Simplex Partitioning via Exponential Clocks and the Multiway-Cut Problem
DOI10.1137/15M1045521zbMath1397.68220OpenAlexW2883925562WikidataQ115525641 ScholiaQ115525641MaRDI QIDQ4577771
Niv Buchbinder, Roy Schwartz, Joseph (Seffi) Naor
Publication date: 3 August 2018
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/15m1045521
Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Randomized algorithms (68W20)
Related Items (2)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A lower bound of \(8/(7+\frac{1}{k-1})\) on the integrality ratio of the Călinescu-Karloff-Rabani relaxation for multiway cut
- Geometric rounding: A dependent randomized rounding scheme
- Minimum 0-extensions of graph metrics
- An improved approximation algorithm of MULTIWAY CUT.
- The geometry of graphs and some of its algorithmic applications
- Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
- A 2-Approximation Algorithm for the Directed Multiway Cut Problem
- Rounding algorithms for a geometric embedding of minimum multiway cut
- Divide-and-conquer approximation algorithms via spreading metrics
- Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
- Approximation algorithms for classification problems with pairwise relationships
- On Earthmover Distance, Metric Labeling, and 0-Extension
- The Complexity of Multiterminal Cuts
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- An O(log k) Approximate Min-Cut Max-Flow Theorem and Approximation Algorithm
- Multiway cuts in node weighted graphs
- Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications
- Multiway cut, pairwise realizable distributions, and descending thresholds
- A Linear Programming Formulation and Approximation Algorithms for the Metric Labeling Problem
- The Hardness of Metric Labeling
- Simplex partitioning via exponential clocks and the multiway cut problem
- Expander flows, geometric embeddings and graph partitioning
- A tight bound on approximating arbitrary metrics by tree metrics
This page was built for publication: Simplex Partitioning via Exponential Clocks and the Multiway-Cut Problem
