Simplex Transformations and the Multiway Cut Problem
From MaRDI portal
Publication:5000653
DOI10.1287/moor.2020.1073OpenAlexW3127886093MaRDI QIDQ5000653
Roy Schwartz, Niv Buchbinder, 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
Cites Work
- 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
- Polynomial time approximation schemes for dense instances of \( \mathcal{NP}\)-hard problems
- Minimum 0-extensions of graph metrics
- An improved approximation algorithm of MULTIWAY CUT.
- The geometry of graphs and some of its algorithmic applications
- Approximation algorithms for minimum \(K\)-cut
- An improved integrality gap for the Călinescu-Karloff-Rabani relaxation for multiway cut
- 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
- Simplex Partitioning via Exponential Clocks and the Multiway-Cut Problem
- Approximation Algorithms for the 0-Extension Problem
- 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
- Expander flows, geometric embeddings and graph partitioning
- A tight bound on approximating arbitrary metrics by tree metrics
- Improving the integrality gap for multiway cut
This page was built for publication: Simplex Transformations and the Multiway Cut Problem
