A lower bound of \(8/(7+\frac{1}{k-1})\) on the integrality ratio of the Călinescu-Karloff-Rabani relaxation for multiway cut

DOI10.1016/S0020-0190(00)00065-XzbMath1339.68204OpenAlexW1985219023MaRDI QIDQ294793

Ari Freund, Howard J. Karloff

Publication date: 16 June 2016

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0020-0190(00)00065-x

zbMATH Keywords

lower boundsgraph algorithmsapproximation ratiomultiway cuts

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items

On the (near) optimality of extended formulations for multi-way cut in social networks ⋮ Simplex Partitioning via Exponential Clocks and the Multiway-Cut Problem ⋮ Approximation Algorithms for CSPs ⋮ Submodular Cost Allocation Problem and Applications ⋮ Optimal 3-terminal cuts and linear programming ⋮ A simple algorithm for the multiway cut problem ⋮ Improving the integrality gap for multiway cut ⋮ Simplex Transformations and the Multiway Cut Problem ⋮ Approximation algorithms for vertex happiness ⋮ On a bidirected relaxation for the MULTIWAY CUT problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Rounding algorithms for a geometric embedding of minimum multiway cut
• On the multiway cut polyhedron
• The Complexity of Multiterminal Cuts
• On minimum 3-cuts and approximating k-cuts using Cut Trees
• Nonlinear formulations and improved randomized approximation algorithms for multicut problems