Simplex transformations and the multiway cut problem

DOI10.1137/1.9781611974782.158MaRDI QIDQ4575907zbMATH OpenOpenAlexFDO

Authors Niv Buchbinder, Roy Schwartz, Baruch Weizman

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

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

Recommendations

• Simplex transformations and the multiway cut problem
• Simplex partitioning via exponential clocks and the multiway cut problem
• Simplex partitioning via exponential clocks and the multiway-cut problem
• A simple algorithm for the multiway cut problem

Cited in

(11)

• _p-norm multiway cut
• Geometric multicut: shortest fences for separating groups of objects in the plane
• Mixed-case community detection problem in social networks: algorithms and analysis
• A simple algorithm for the multiway cut problem
• Simplex partitioning via exponential clocks and the multiway-cut problem
• Simplex transformations and the multiway cut problem
• Improving the integrality gap for multiway cut
• Approximating Requirement Cut via a Configuration LP
• A local search approximation algorithm for the multiway cut problem
• Lower bounds on 0-extension with Steiner nodes
• Experimental evaluation of a local search approximation algorithm for the multiway cut problem

This page was built for publication: Simplex transformations and the multiway cut problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4575907)