标题： 改进的多流-多割间隙下界 显示英文标题

标题： Improved Lower Bounds on Multiflow-Multicut Gaps

摘要： 给定一组源-汇对，最大多流问题要求找出在它们之间可行传输的最大总流量。 最小多割是多流的一个对偶问题，它寻求移除后能断开所有源-汇对的边的最小成本集合。 很容易看出，最小多割的值至少等于最大多流的值，它们的比值称为多流-多割间隙。 经典的最大流最小割定理指出，当只有一对源-汇时，该间隙恰好为一。 然而，在一般情况下，众所周知该间隙可以变得任意大。 在本文中，我们研究平面图类中的这一间隙，并建立了改进的下界结果。 特别是，我们证明对于平面图类，该间隙至少为$\frac{20}{9}$，这优于几十年前的下界2。 更重要的是，我们开发了证明这种下界的新技术，这些技术可能在其他情况下也有用。 显示英文摘要

摘要： Given a set of source-sink pairs, the maximum multiflow problem asks for the maximum total amount of flow that can be feasibly routed between them. The minimum multicut, a dual problem to multiflow, seeks the minimum-cost set of edges whose removal disconnects all the source-sink pairs. It is easy to see that the value of the minimum multicut is at least that of the maximum multiflow, and their ratio is called the multiflow-multicut gap. The classical max-flow min-cut theorem states that when there is only one source-sink pair, the gap is exactly one. However, in general, it is well known that this gap can be arbitrarily large. In this paper, we study this gap for classes of planar graphs and establish improved lower bound results. In particular, we show that this gap is at least $\frac{20}{9}$ for the class of planar graphs, improving upon the decades-old lower bound of 2. More importantly, we develop new techniques for proving such a lower bound, which may be useful in other settings as well.