Simplex transformations and the multiway cut problem
From MaRDI portal
Publication:5000653
DOI10.1287/MOOR.2020.1073OpenAlexW3127886093MaRDI QIDQ5000653FDOQ5000653
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
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
- Rounding algorithms for a geometric embedding of minimum multiway cut
Cites Work
- Polynomial time approximation schemes for dense instances of \( \mathcal{NP}\)-hard problems
- The geometry of graphs and some of its algorithmic applications
- Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
- The Complexity of Multiterminal Cuts
- Multiway cuts in node weighted graphs
- Expander flows, geometric embeddings and graph partitioning
- A tight bound on approximating arbitrary metrics by tree metrics
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
- Rounding algorithms for a geometric embedding of minimum multiway cut
- A lower bound of \(8/(7+\frac{1}{k-1})\) on the integrality ratio of the Călinescu-Karloff-Rabani relaxation for multiway cut
- Title not available (Why is that?)
- An O(log k) Approximate Min-Cut Max-Flow Theorem and Approximation Algorithm
- Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications
- Approximation algorithms for classification problems with pairwise relationships
- Divide-and-conquer approximation algorithms via spreading metrics
- An improved approximation algorithm of MULTIWAY CUT.
- Minimum 0-extensions of graph metrics
- Approximation algorithms for minimum \(K\)-cut
- Title not available (Why is that?)
- Approximation Algorithms for the 0-Extension Problem
- Multiway cut, pairwise realizable distributions, and descending thresholds
- A 2-approximation algorithm for the directed multiway cut problem
- A Linear Programming Formulation and Approximation Algorithms for the Metric Labeling Problem
- The Hardness of Metric Labeling
- Title not available (Why is that?)
- On earthmover distance, metric labeling, and 0-extension
- An improved integrality gap for the Călinescu-Karloff-Rabani relaxation for multiway cut
- Improving the integrality gap for multiway cut
- 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)
