Approximating Requirement Cut via a Configuration LP
From MaRDI portal
Publication:6084417
DOI10.4230/lipics.approx/random.2020.53OpenAlexW3082232337MaRDI QIDQ6084417
Publication date: 31 October 2023
Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2020/12656/pdf/LIPIcs-APPROX53.pdf/
Cites Work
- Unnamed Item
- Unnamed Item
- Approximation algorithms for requirement cut on graphs
- The multi-multiway cut problem
- An improved approximation algorithm for requirement cut
- An improved approximation algorithm of MULTIWAY CUT.
- An approximate max-flow min-cut relation for undirected multicommodity flow, with applications
- The geometry of graphs and some of its algorithmic applications
- Fréchet embeddings of negative type metrics
- Rounding algorithms for a geometric embedding of minimum multiway cut
- Approximation Algorithms for Steiner and Directed Multicuts
- Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
- The Complexity of Multiterminal Cuts
- Finding k Cuts within Twice the Optimal
- Simplex Transformations and the Multiway Cut Problem
- Simplex Partitioning via Exponential Clocks and the Multiway-Cut Problem
- Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications
- Embeddings of negative-type metrics and an improved approximation to generalized sparsest cut
- Multiway cut, pairwise realizable distributions, and descending thresholds
- Euclidean distortion and the sparsest cut
- The Steiner k-Cut Problem
- Geometry of cuts and metrics
This page was built for publication: Approximating Requirement Cut via a Configuration LP