Simplex partitioning via exponential clocks and the multiway cut problem
From MaRDI portal
Publication:5495824
DOI10.1145/2488608.2488675zbMath1293.05286OpenAlexW2132805234MaRDI QIDQ5495824
Joseph (Seffi) Naor, Roy Schwartz, Niv Buchbinder
Publication date: 7 August 2014
Published in: Proceedings of the forty-fifth annual ACM symposium on Theory of Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/2488608.2488675
Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)
Related Items
Solving \((k-1)\)-stable instances of \texttt{k-terminal cut} with isolating cuts, On the (near) optimality of extended formulations for multi-way cut in social networks, Experimental evaluation of a local search approximation algorithm for the multiway cut problem, Approximation algorithms for stochastic combinatorial optimization problems, Approximation and hardness results for the max \(k\)-uncut problem, Improved Approximation Algorithms for the Maximum Happy Vertices and Edges Problems, \(\ell_p\)-norm multiway cut, Simplex Partitioning via Exponential Clocks and the Multiway-Cut Problem, Approximation and Hardness Results for the Max k-Uncut Problem, A local search approximation algorithm for the multiway cut problem, An \(O^\ast(1.84^k)\) parameterized algorithm for the multiterminal cut problem, Approximation Algorithms for CSPs, Improved approximation algorithms for the maximum happy vertices and edges problems, A simple algorithm for the multiway cut problem, Improving the integrality gap for multiway cut, Approximation algorithms for vertex happiness, Isolation branching: a branch and bound algorithm for the \(k \)-terminal cut problem
