Simplex partitioning via exponential clocks and the multiway-cut problem

DOI10.1137/15M1045521MaRDI QIDQ4577771zbMATH OpenOpenAlexWikidataFDO

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

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

zbMATH Keywords

approximation algorithmscutmultiwayrandomizedsimplex

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Randomized algorithms (68W20) Approximation algorithms (68W25)

Recommendations

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

Cites work

• A 2-approximation algorithm for the directed multiway cut problem
• A Linear Programming Formulation and Approximation Algorithms for the Metric Labeling Problem
• A lower bound of \(8/(7+\frac{1}{k-1})\) on the integrality ratio of the Călinescu-Karloff-Rabani relaxation for multiway cut
• A tight bound on approximating arbitrary metrics by tree metrics
• An O(log k) Approximate Min-Cut Max-Flow Theorem and Approximation Algorithm
• An improved approximation algorithm of MULTIWAY CUT.
• Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications
• Approximation algorithms for classification problems with pairwise relationships, metric labeling and Markov random fields
• Approximation algorithms for the 0-extension problem
• Divide-and-conquer approximation algorithms via spreading metrics
• Expander flows, geometric embeddings and graph partitioning
• Geometric rounding: A dependent randomized rounding scheme
• scientific article; zbMATH DE number 5485510 (Why is no real title available?)
• scientific article; zbMATH DE number 1263204 (Why is no real title available?)
• scientific article; zbMATH DE number 1342124 (Why is no real title available?)
• scientific article; zbMATH DE number 1145157 (Why is no real title available?)
• scientific article; zbMATH DE number 2079348 (Why is no real title available?)
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Minimum 0-extensions of graph metrics
• Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
• Multiway cut, pairwise realizable distributions, and descending thresholds
• Multiway cuts in node weighted graphs
• On earthmover distance, metric labeling, and 0-extension
• Simplex partitioning via exponential clocks and the multiway cut problem
• The Complexity of Multiterminal Cuts
• The geometry of graphs and some of its algorithmic applications
• The Hardness of Metric Labeling
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)

Cited in

(6)

• From graph to hypergraph multiway partition: is the single threshold the only route?
• Simplex transformations and the multiway cut problem
• Simplex transformations and the multiway cut problem
• Simplex partitioning via exponential clocks and the multiway cut problem
• Approximating Requirement Cut via a Configuration LP
• Multiway cuts with a choice of representatives

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 Q4577771)