Coarse Differentiation and Multi-flows in Planar Graphs
From MaRDI portal
Publication:3603468
DOI10.1007/978-3-540-74208-1_17zbMATH Open1171.90535arXiv0804.1573OpenAlexW2805712439MaRDI QIDQ3603468FDOQ3603468
Authors: James R. Lee, Prasad Raghavendra 
Publication date: 17 February 2009
Published in: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)
Abstract: We show that the multi-commodity max-flow/min-cut gap for series-parallel graphs can be as bad as 2, matching a recent upper bound Chakrabarti, Jaffe, Lee, and Vincent for this class, and resolving one side of a conjecture of Gupta, Newman, Rabinovich, and Sinclair. This also improves the largest known gap for planar graphs from 3/2 to 2, yielding the first lower bound that doesn't follow from elementary calculations. Our approach uses the {em coarse differentiation} method of Eskin, Fisher, and Whyte in order to lower bound the distortion for embedding a particular family of shortest-path metrics into .
Full work available at URL: https://arxiv.org/abs/0804.1573
Recommendations
- Coarse differentiation and multi-flows in planar graphs
- Flow-Cut Gaps and Face Covers in Planar Graphs
- On constant multi-commodity flow-cut gaps for families of directed minor-free graphs
- Improved bounds for the max-flow min-multicut ratio for planar and \(K_{r,r}\)-free graphs
- Improved bounds on the max-flow min-cut ratio for multicommodity flows
Cited In (2)
This page was built for publication: Coarse Differentiation and Multi-flows in Planar Graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3603468)
