An improved integrality gap for the Călinescu-Karloff-Rabani relaxation for multiway cut

DOI10.1007/978-3-319-59250-3_4zbMath1418.90267arXiv1611.05530OpenAlexW2557153431MaRDI QIDQ2401143

Haris Angelidakis, Yury Makarychev, Pasin Manurangsi

Publication date: 31 August 2017

Full work available at URL: https://arxiv.org/abs/1611.05530

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27)

Related Items (8)

Solving \((k-1)\)-stable instances of \texttt{k-terminal cut} with isolating cuts ⋮ \(\ell_p\)-norm multiway cut ⋮ Global and fixed-terminal cuts in digraphs ⋮ Odd Multiway Cut in Directed Acyclic Graphs ⋮ A simple algorithm for the multiway cut problem ⋮ Improving the integrality gap for multiway cut ⋮ Beating the 2-approximation factor for global bicut ⋮ Simplex Transformations and the Multiway Cut Problem

This page was built for publication: An improved integrality gap for the Călinescu-Karloff-Rabani relaxation for multiway cut