Improving the integrality gap for multiway cut

DOI10.1007/s10107-020-01485-2zbMath1450.90038OpenAlexW3009048356MaRDI QIDQ5918912

Tamás Király, Vivek Madan, Kristóf Bérczi, Karthekeyan Chandrasekaran

Publication date: 28 August 2020

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: http://real.mtak.hu/113033/1/egres-19-04.pdf

zbMATH Keywords

combinatorial optimizationapproximationintegrality gapmultiway cut

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Related Items (5)

\(\ell_p\)-norm multiway cut ⋮ Mean isoperimetry with control on outliers: exact and approximation algorithms ⋮ Fixed parameter approximation scheme for min-max \(k\)-cut ⋮ Fixed parameter approximation scheme for min-max \(k\)-cut ⋮ Simplex Transformations and the Multiway Cut Problem

Cites Work

• Unnamed Item
• A lower bound of \(8/(7+\frac{1}{k-1})\) on the integrality ratio of the Călinescu-Karloff-Rabani relaxation for multiway cut
• An improved approximation algorithm of MULTIWAY CUT.
• An improved integrality gap for the Călinescu-Karloff-Rabani relaxation for multiway cut
• Optimal 3-terminal cuts and linear programming
• Rounding algorithms for a geometric embedding of minimum multiway cut
• The Complexity of Multiterminal Cuts
• Simplex Transformations and the Multiway Cut Problem
• Multiway cut, pairwise realizable distributions, and descending thresholds
• Sperner's Colorings, Hypergraph Labeling Problems and Fair Division
• Simplex partitioning via exponential clocks and the multiway cut problem

This page was built for publication: Improving the integrality gap for multiway cut