An O(log k) Approximate Min-Cut Max-Flow Theorem and Approximation Algorithm

DOI10.1137/S0097539794285983zbMath0910.05038OpenAlexW2107881198MaRDI QIDQ4388872

Yuval Rabani, Yonatan Aumann

Publication date: 10 May 1998

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0097539794285983

zbMATH Keywords

approximation algorithmnetwork flowmulticommodity flowconcurrent flowsparse cuts

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Deterministic network models in operations research (90B10) Paths and cycles (05C38)

Related Items (38)

Sketching and Embedding are Equivalent for Norms ⋮ A note on multiflows and treewidth ⋮ Approximation algorithms for the weighted \(t\)-uniform sparsest cut and some other graph partitioning problems ⋮ Coarse differentiation and multi-flows in planar graphs ⋮ Approximate \(k\)-Steiner forests via the Lagrangian relaxation technique with internal preprocessing ⋮ \(\ell ^2_2\) spreading metrics for vertex ordering problems ⋮ Approximation algorithms for requirement cut on graphs ⋮ Vertical perimeter versus horizontal perimeter ⋮ Semidefinite programming in combinatorial optimization ⋮ Terminal embeddings ⋮ Towards duality of multicommodity multiroute cuts and flows: multilevel ball-growing ⋮ Simplex Partitioning via Exponential Clocks and the Multiway-Cut Problem ⋮ Metric differentiation, monotonicity and maps to \(L^{1}\) ⋮ Mean isoperimetry with control on outliers: exact and approximation algorithms ⋮ Cut-sufficient directed 2-commodity multiflow topologies ⋮ An introduction to the Ribe program ⋮ Compression bounds for Lipschitz maps from the Heisenberg group to \(L_{1}\) ⋮ Unnamed Item ⋮ On the optimality of gluing over scales ⋮ Models and methods for solving the problem of network vulnerability ⋮ Euclidean distortion and the sparsest cut ⋮ Pathwidth, trees, and random embeddings ⋮ Sparsest cuts and concurrent flows in product graphs. ⋮ Inapproximability of edge-disjoint paths and low congestion routing on undirected graphs ⋮ Advances in metric embedding theory ⋮ Cut problems in graphs with a budget constraint ⋮ A new approach to low-distortion embeddings of finite metric spaces into non-superreflexive Banach spaces ⋮ Nonembeddability theorems via Fourier analysis ⋮ Meet and merge: approximation algorithms for confluent flows ⋮ New algorithms for maximum disjoint paths based on tree-likeness ⋮ A tight bound on approximating arbitrary metrics by tree metrics ⋮ Hallucination Helps: Energy Efficient Virtual Circuit Routing ⋮ A simple algorithm for the multiway cut problem ⋮ Multicommodity flows and cuts in polymatroidal networks ⋮ Simplex Transformations and the Multiway Cut Problem ⋮ Metric structures in \(L_1\): dimension, snowflakes, and average distortion ⋮ The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative-Type Metrics into ℓ ₁ ⋮ The legacy of Jean Bourgain in geometric functional analysis

This page was built for publication: An O(log k) Approximate Min-Cut Max-Flow Theorem and Approximation Algorithm