Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR08-060 | 10th April 2008 00:00

Coarse Differentiation and Multi-flows in Planar Graphs

RSS-Feed




TR08-060
Authors: James R. Lee, Prasad Raghavendra
Publication: 7th June 2008 01:04
Downloads: 3411
Keywords: 


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 by Chakrabarti.et.al 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 Coarse Differentiation method of Eskin, Fischer, and Whyte in order to lower bound the distortion for embedding a particular family of shortest-path metrics into L_1.



ISSN 1433-8092 | Imprint