Simplex partitioning via exponential clocks and the multiway cut problem

DOI10.1145/2488608.2488675MaRDI QIDQ5495824zbMATH OpenOpenAlexFDO

Authors Niv Buchbinder, Joseph (Seffi) Naor, Roy Schwartz

Publication date 7 August 2014

Published in Proceedings of the forty-eighth annual ACM symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/2488608.2488675

zbMATH Keywords

approximation algorithmexponential clocksmultiway cut problemsimplex partitioning

Mathematics Subject Classification ID

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)

Recommendations

• Simplex partitioning via exponential clocks and the multiway-cut problem
• SOFSEM 2006: Theory and Practice of Computer Science
• Approximation algorithms for the Bipartite Multicut problem
• scientific article; zbMATH DE number 2081031
• scientific article; zbMATH DE number 1538871
• Cutting plane algorithms for solving a stochastic edge-partition problem
• Computing and Combinatorics
• A polynomial-time approximation scheme for planar multiway cut
• Greedy splitting algorithms for approximating multiway partition problems

Cited in

(24)

• Approximation and hardness results for the max \(k\)-uncut problem
• Improved approximation algorithms for the maximum happy vertices and edges problems
• Isolation branching: a branch and bound algorithm for the \(k \)-terminal cut problem
• 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
• _p-norm multiway cut
• A simple algorithm for the multiway cut problem
• Approximation algorithms for vertex happiness
• An O^(1.84ᵏ) parameterized algorithm for the multiterminal cut problem
• Approximation algorithms for stochastic combinatorial optimization problems
• From graph to hypergraph multiway partition: is the single threshold the only route?
• Approximation and hardness results for the max \(k\)-uncut problem
• Improved approximation algorithms for the maximum happy vertices and edges problems
• Simplex transformations and the multiway cut problem
• Simplex partitioning via exponential clocks and the multiway-cut problem
• Approximation Algorithms for CSPs
• Simplex transformations and the multiway cut problem
• Local distribution and the symmetry gap: approximability of multiway partitioning problems
• Improving the integrality gap for multiway cut
• A local search approximation algorithm for the multiway cut problem
• Lower bounds on 0-extension with Steiner nodes
• Monotone submodular multiway partition
• Multiway cuts with a choice of representatives
• Experimental evaluation of a local search approximation algorithm for the multiway cut problem

This page was built for publication: Simplex partitioning via exponential clocks and the multiway cut problem

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