Simplex transformations and the multiway cut problem

DOI10.1287/MOOR.2020.1073MaRDI QIDQ5000653zbMATH OpenOpenAlexFDO

Authors Niv Buchbinder, Roy Schwartz, Baruch Weizman

Publication date 15 July 2021

Published in Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1287/moor.2020.1073

zbMATH Keywords

approximation algorithmsrandomized roundingmultiway cut

Mathematics Subject Classification ID

Approximation algorithms (68W25)

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

Cites work

• scientific article; zbMATH DE number 5485510 (Why is no real title available?)
• scientific article; zbMATH DE number 1342124 (Why is no real title available?)
• scientific article; zbMATH DE number 2079348 (Why is no real title available?)
• 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.
• An improved integrality gap for the Călinescu-Karloff-Rabani relaxation for multiway cut
• Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications
• Approximation Algorithms for the 0-Extension Problem
• Approximation algorithms for classification problems with pairwise relationships, metric labeling and Markov random fields
• Approximation algorithms for minimum \(K\)-cut
• Divide-and-conquer approximation algorithms via spreading metrics
• Expander flows, geometric embeddings and graph partitioning
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Improving the integrality gap for multiway cut
• 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
• Polynomial time approximation schemes for dense instances of \( \mathcal{NP}\)-hard problems
• Simplex partitioning via exponential clocks and the multiway-cut problem
• The Complexity of Multiterminal Cuts
• The Hardness of Metric Labeling
• The geometry of graphs and some of its algorithmic applications
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)

Cited in

(2)

• Simplex transformations and the multiway cut problem
• Simplex partitioning via exponential clocks and 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 Q5000653)