Simplex Transformations and the Multiway Cut Problem

DOI10.1137/1.9781611974782.158zbMath1410.05193OpenAlexW4233880474MaRDI QIDQ4575907

Baruch Weizman, Roy Schwartz, Niv Buchbinder

Publication date: 16 July 2018

Published in: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/1.9781611974782.158

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (8)

Experimental evaluation of a local search approximation algorithm for the multiway cut problem ⋮ \(\ell_p\)-norm multiway cut ⋮ A local search approximation algorithm for the multiway cut problem ⋮ Geometric multicut: shortest fences for separating groups of objects in the plane ⋮ Mixed-case community detection problem in social networks: algorithms and analysis ⋮ Approximating Requirement Cut via a Configuration LP ⋮ A simple algorithm for the multiway cut problem ⋮ Improving the integrality gap for multiway cut

This page was built for publication: Simplex Transformations and the Multiway Cut Problem