论文标题
Okamura-Seymour定理的近似概括
An Approximate Generalization of the Okamura-Seymour Theorem
论文作者
论文摘要
我们考虑了平面图中多商品流的问题。 Okamura和Seymour表明，如果所有需求都出现在一个面上，那么切割条件就足以满足路线需求。我们考虑以下此设置的概括，并证明最大流量最大剪切定理：对于每个需求边缘，都存在一个包含其终点的脸部。我们表明，切割条件足以将$ω（1）$ - 所有需求的一部分路由。为了证明这一点，我们给出了平面度量的$ l_1 $ - 填充，该度量大约可以保留同一面上所有点之间的距离。
We consider the problem of multicommodity flows in planar graphs. Okamura and Seymour showed that if all the demands are incident on one face, then the cut-condition is sufficient for routing demands. We consider the following generalization of this setting and prove an approximate max flow-min cut theorem: for every demand edge, there exists a face containing both its end points. We show that the cut-condition is sufficient for routing $Ω(1)$-fraction of all the demands. To prove this, we give a $L_1$-embedding of the planar metric which approximately preserves distance between all pair of points on the same face.
