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-XzbMATH Open1339.68204OpenAlexW1985219023MaRDI QIDQ294793FDOQ294793

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

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.

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)

Cites Work

• Title not available (Why is that?)
• The Complexity of Multiterminal Cuts
• Title not available (Why is that?)
• On the multiway cut polyhedron
• Title not available (Why is that?)
• Title not available (Why is that?)
• On minimum 3-cuts and approximating k-cuts using cut trees
• Nonlinear formulations and improved randomized approximation algorithms for multicut problems

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 CSPs
• Approximation algorithms for vertex happiness
• 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)