Approximating Requirement Cut via a Configuration LP

DOI10.4230/lipics.approx/random.2020.53OpenAlexW3082232337MaRDI QIDQ6084417

Unnamed Author, Roy Schwartz

Publication date: 31 October 2023

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2020/12656/pdf/LIPIcs-APPROX53.pdf/

zbMATH Keywords

approximationsparsest cutmetric embeddingrequirement cut

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Approximation algorithms (68W25) Randomized algorithms (68W20)

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