论文标题
两种商品流量等效于几乎线性时间的线性编程
Two-Commodity Flow is Equivalent to Linear Programming under Nearly-Linear Time Reductions
论文作者
论文摘要
我们给出了将近线性的时间缩短，将任何线性程序编码为2个商品流量问题，只有很小的大小爆炸。在与现代快速求解器用于线性程序相似的轻度假设下，我们的还原仅导致该程序规模的多层次乘法增加，并且在几乎线的时间内运行。我们的还原适用于高临界近似算法和精确的算法。给定对2个商品流问题的近似解决方案，我们可以在线性时间中提取线性程序的解决方案，而多项式因子的误差增加。这意味着任何解决2-商品流问题的算法都可以同时解决线性程序。给定具有边缘能力和两个源链接对的有向图，2-商品流问题的目标是最大化两个源链接对之间的流量总和，约为边缘能力和流量保护。 2商品流可以直接写为线性程序，因此我们在这两个类别的问题之间建立了几乎密度的等效性。 我们的证明遵循ITAI将线性程序多项式时间缩短到2商品流问题（JACM'78）的轮廓。 ITAI的减少表明，准确求解2个商品流量和确切求解线性编程是多项式时间等效的。我们改善了ITAI的减少，以几乎保留每个步骤中的问题表示规模。此外，我们建立了一个误差，用于大约求解还原中的每个中间问题，并表明累积误差是多项式界限的。我们指出的是，我们的还原不会在强烈的多项式时间内进行，并且无论是2-商品流量和线性编程是否等效于强烈的多项式时间，它是开放的。
We give a nearly-linear time reduction that encodes any linear program as a 2-commodity flow problem with only a small blow-up in size. Under mild assumptions similar to those employed by modern fast solvers for linear programs, our reduction causes only a polylogarithmic multiplicative increase in the size of the program and runs in nearly-linear time. Our reduction applies to high-accuracy approximation algorithms and exact algorithms. Given an approximate solution to the 2-commodity flow problem, we can extract a solution to the linear program in linear time with only a polynomial factor increase in the error. This implies that any algorithm that solves the 2-commodity flow problem can solve linear programs in essentially the same time. Given a directed graph with edge capacities and two source-sink pairs, the goal of the 2-commodity flow problem is to maximize the sum of the flows routed between the two source-sink pairs subject to edge capacities and flow conservation. A 2-commodity flow can be directly written as a linear program, and thus we establish a nearly-tight equivalence between these two classes of problems. Our proof follows the outline of Itai's polynomial-time reduction of a linear program to a 2-commodity flow problem (JACM'78). Itai's reduction shows that exactly solving 2-commodity flow and exactly solving linear programming are polynomial-time equivalent. We improve Itai's reduction to nearly preserve the problem representation size in each step. In addition, we establish an error bound for approximately solving each intermediate problem in the reduction, and show that the accumulated error is polynomially bounded. We remark that our reduction does not run in strongly polynomial time and that it is open whether 2-commodity flow and linear programming are equivalent in strongly polynomial time.
