An O(log k) Approximate Min-Cut Max-Flow Theorem and Approximation Algorithm
From MaRDI portal
Publication:4388872
Recommendations
Cited in
(47)- Semidefinite programming in combinatorial optimization
- Sparsest cuts and concurrent flows in product graphs.
- Vertical perimeter versus horizontal perimeter
- New algorithms for maximum disjoint paths based on tree-likeness
- An introduction to the Ribe program
- Models and methods for solving the problem of network vulnerability
- The max-flow min-cut property and \(\pm 1\)-resistant sets
- A simple algorithm for the multiway cut problem
- Terminal embeddings
- Pathwidth, trees, and random embeddings
- Cut problems in graphs with a budget constraint
- Nonembeddability theorems via Fourier analysis
- Meet and merge: approximation algorithms for confluent flows
- Metric structures in \(L_1\): dimension, snowflakes, and average distortion
- Max flow and min cut with bounded-length paths: complexity, algorithms, and approximation
- Mean isoperimetry with control on outliers: exact and approximation algorithms
- Approximation algorithms for the weighted t-uniform sparsest cut and some other graph partitioning problems
- Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
- Towards duality of multicommodity multiroute cuts and flows: multilevel ball-growing
- An Exact Sublinear Algorithm for the Max-Flow, Vertex Disjoint Paths and Communication Problems on Random Graphs
- Compression bounds for Lipschitz maps from the Heisenberg group to \(L_{1}\)
- Sketching and embedding are equivalent for norms
- Simplex partitioning via exponential clocks and the multiway-cut problem
- scientific article; zbMATH DE number 6846417 (Why is no real title available?)
- An improved direct labeling method for the max-flow min-cut computation in large hypergraphs and applications
- Improved approximations for the minimum-cut ratio and the flux
- Simplex transformations and the multiway cut problem
- Approximating sparsest cut in low rank graphs via embeddings from approximately low-dimensional spaces
- Hallucination helps: energy efficient virtual circuit routing
- A new approach to low-distortion embeddings of finite metric spaces into non-superreflexive Banach spaces
- Streaming Lower Bounds for Approximating MAX-CUT
- Euclidean distortion and the sparsest cut
- The unique games conjecture, integrality gap for cut problems and embeddability of negative-type metrics into _1
- The legacy of Jean Bourgain in geometric functional analysis
- Advances in metric embedding theory
- A tight bound on approximating arbitrary metrics by tree metrics
- Metric differentiation, monotonicity and maps to \(L^{1}\)
- Cut-sufficient directed 2-commodity multiflow topologies
- On the optimality of gluing over scales
- Inapproximability of edge-disjoint paths and low congestion routing on undirected graphs
- Cut-sufficient directed 2-commodity multiflow topologies
- Direct product multicommodity max-concurrent-flow min-sparse-cut theorem
- A note on multiflows and treewidth
- 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
This page was built for publication: An O(log k) Approximate Min-Cut Max-Flow Theorem and Approximation Algorithm
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4388872)
