Optimal 3-terminal cuts and linear programming
From MaRDI portal
Publication:2490332
DOI10.1007/s10107-005-0668-2zbMath1134.90515OpenAlexW2096411231MaRDI QIDQ2490332
Lawrence Tang, William H. Cunningham, Kevin K. H. Cheung
Publication date: 2 May 2006
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10107-005-0668-2
Programming involving graphs or networks (90C35) Linear programming (90C05) Combinatorial optimization (90C27)
Related Items (9)
Extended cuts ⋮ \(\ell_p\)-norm multiway cut ⋮ Global and fixed-terminal cuts in digraphs ⋮ Approximation algorithms for \(k\)-hurdle problems ⋮ A tight \(\sqrt{2} \)-approximation for linear 3-cut ⋮ Optimal 3-terminal cuts and linear programming ⋮ Approximation Algorithms for k-Hurdle Problems ⋮ Improving the integrality gap for multiway cut ⋮ Beating the 2-approximation factor for global bicut
Cites Work
- Unnamed Item
- Unnamed Item
- 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.
- Optimal 3-terminal cuts and linear programming
- Rounding algorithms for a geometric embedding of minimum multiway cut
- On the multiway cut polyhedron
- The Complexity of Multiterminal Cuts
This page was built for publication: Optimal 3-terminal cuts and linear programming
