Finite Termination of "Augmenting Path" Algorithms in the Presence of Irrational Problem Data
Finite Termination of "Augmenting Path" Algorithms in the Presence of Irrational Problem Data
复制标题
存在非理性问题数据时“增广路径”算法的有限终止
DOI：
--
复制
发表时间：
2006
期刊：
影响因子：
--
通讯作者：
Nicole Immorlica
中科院分区：
文献类型：
--
作者：
B. C. Dean;M. Goemans;Nicole Immorlica
本文考虑了两个类似的图算法，工作通过反复增加流量沿着增广路径：福特-富克尔森算法的最大流问题和Gale-Shapley算法的稳定分配问题（多对多的推广的稳定匹配问题）。当给定积分输入数据时，这两种算法显然都会终止。对于实值输入数据，先前已知如果通过广度优先搜索选择扩充路径，则Ford-Fulkerson算法在多项式时间内运行，但是如果以任意方式选择扩充路径，则算法可能无法终止。然而，Gale-Shapley算法在实值数据上的性能尚未得到解决。我们的主要结果表明，与Ford-Fulkerson算法相比，Gale-Shapley算法在实值数据上总是在有限时间内终止。虽然Gale-Shapley算法在最坏情况下可能需要指数时间，但由于其简单性以及对于实践中遇到的许多输入通常运行非常快（即使在次线性时间）的事实，它在实践中是一种流行的算法。我们还研究了增强路径时，通过深度优先搜索，在实践中常见的实施方式选择的福特-富克尔森算法。我们证明，像广度优先搜索，深度优先搜索也导致有限终止（虽然不一定在多项式时间）。
This paper considers two similar graph algorithms that work by repeatedly increasing flow along augmenting paths: the Ford-Fulkerson algorithm for the maximum flow problem and the Gale-Shapley algorithm for the stable allocation problem (a many-to-many generalization of the stable matching problem). Both algorithms clearly terminate when given integral input data. For real-valued input data, it was previously known that the Ford-Fulkerson algorithm runs in polynomial time if augmenting paths are chosen via breadth-first search, but that the algorithm might fail to terminate if augmenting paths are chosen in an arbitrary fashion. However, the performance of the Gale-Shapley algorithm on real-valued data was unresolved. Our main result shows that, in contrast to the Ford-Fulkerson algorithm, the Gale-Shapley algorithm always terminates in finite time on real-valued data. Although the Gale-Shapley algorithm may take exponential time in the worst case, it is a popular algorithm in practice due to its simplicity and the fact that it often runs very quickly (even in sublinear time) for many inputs encountered in practice. We also study the Ford-Fulkerson algorithm when augmenting paths are chosen via depth-first search, a common implementation in practice. We prove that, like breadth-first search, depth-first search also leads to finite termination (although not necessarily in polynomial time).