论文标题
整数平面多滚力最大化：流动缝隙和四分之一的附属物
Integer Plane Multiflow Maximisation : Flow-Cut Gap and One-Quarter-Approximation
论文作者
论文摘要
在本文中，我们绑定了最大平面多流问题的整体差距和近似比，并在流距离间隙上推断边界。平面性意味着在这里供需图是平面的。我们首先证明，有一个值的多量至少是最低多速度的一半。然后，我们将展示如何将任何多动物转换为最原始多圈的一半值之一。最后，我们将任何一半企业的多动圈围成一个整数多圈，在多项式时间内最多再次损失，在多项式时间内，达到了$ 1/4 $ - APPROXIMATION算法，用于飞机中最大的整数多槽，以及一个整数 - 流式 - flow-flow-cut-cut-cut abe $ 8 $ $ 8 $。
In this paper, we bound the integrality gap and the approximation ratio for maximum plane multiflow problems and deduce bounds on the flow-cut-gap. Planarity means here that the union of the supply and demand graph is planar. We first prove that there exists a multiflow of value at least half of the capacity of a minimum multicut. We then show how to convert any multiflow into a half-integer one of value at least half of the original multiflow. Finally, we round any half-integer multiflow into an integer multiflow, losing again at most half of the value, in polynomial time, achieving a $1/4$-approximation algorithm for maximum integer multiflows in the plane, and an integer-flow-cut gap of $8$.
