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

approximation ratiograph algorithmslower boundsmultiway cuts

Mathematics Subject Classification ID

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

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

(13)

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

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)