论文标题
完全平面边缘路径的近似算法
An Approximation Algorithm for Fully Planar Edge-Disjoint Paths
论文作者
论文摘要
如果供应图和需求边缘形成平面图，我们为边缘 - 偶口路径问题的最大化版本设计了一种恒定因素近似算法。按平面二元性，这等同于在平面图中的包装切割，因此每个切割都完全包含一个需求边缘。我们还表明，天然线性编程松弛具有恒定的完整性差距，产生了近似的最大multiflow min-multicut定理。
We devise a constant-factor approximation algorithm for the maximization version of the edge-disjoint paths problem if the supply graph together with the demand edges form a planar graph. By planar duality this is equivalent to packing cuts in a planar graph such that each cut contains exactly one demand edge. We also show that the natural linear programming relaxations have constant integrality gap, yielding an approximate max-multiflow min-multicut theorem.
