Simplex Transformations and the Multiway Cut Problem

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)