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

DOI10.1016/S0020-0190(00)00065-XMaRDI QIDQ294793zbMATH OpenOpenAlexFDO

Authors Ari Freund, Howard 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 algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Recommendations

• An improved integrality gap for the Călinescu-Karloff-Rabani relaxation for multiway cut
• scientific article; zbMATH DE number 1775387
• An improved approximation algorithm of MULTIWAY CUT.

Cites work

• scientific article; zbMATH DE number 176254 (Why is no real title available?)
• scientific article; zbMATH DE number 1263204 (Why is no real title available?)
• scientific article; zbMATH DE number 1342124 (Why is no real title available?)
• scientific article; zbMATH DE number 1775387 (Why is no real title available?)
• Nonlinear formulations and improved randomized approximation algorithms for multicut problems
• On minimum 3-cuts and approximating k-cuts using cut trees
• On the multiway cut polyhedron
• The Complexity of Multiterminal Cuts

Cited in

(11)

• An improved integrality gap for the Călinescu-Karloff-Rabani relaxation for multiway cut
• A simple algorithm for the multiway cut problem
• On a bidirected relaxation for the MULTIWAY CUT problem
• On the (near) optimality of extended formulations for multi-way cut in social networks
• Improving the integrality gap for multiway cut
• Simplex partitioning via exponential clocks and the multiway-cut problem
• Approximation algorithms for vertex happiness
• Approximation Algorithms for CSPs
• Optimal 3-terminal cuts and linear programming
• Submodular Cost Allocation Problem and Applications
• Simplex transformations and the multiway cut problem

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q294793)