Coarse Differentiation and Multi-flows in Planar Graphs

Coarse Differentiation and Multi-flows in Planar Graphs
复制标题

平面图中的粗微分和多流

DOI：
--
复制
发表时间：
2007
期刊：
International Workshop and International Workshop on Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
影响因子：
--
通讯作者：
P. Raghavendra
P. Raghavendra
中科院分区：
--
文献类型：
--
作者：
James R. Lee;P. Raghavendra

文献摘要

被引文献

相似文献

摘要我们证明了系列-并行图的多商品最大流量/最小切差可以差到2，匹配了这个类最近的上界（Chakrabarti等人在第49届计算机科学基础年度研讨会上，pp. 761 - 770,2008），并解决了Gupta， Newman， Rabinovich和Sinclair猜想的一面。这也改进了平面图的已知最大间隙
AbstractWe 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 et al. in 49th Annual Symposium on Foundations of Computer Science, pp. 761–770, 2008) 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 $frac{3}{2}$ to 2, yielding the first lower bound that does not follow from elementary calculations. Our approach uses the 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 L1.