A simple GAP-canceling algorithm for the generalized maximum flow problem

• 成果类型: Article
• 署名作者: Restrepo, Mateo; Williamson, David P.
• 署名单位: Cornell University; Cornell University
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-007-0183-8
• 发表日期: 2009
• 页码: 47-74
• 关键词: minimum-cost flow; circulation problem; 2 variables; Combinatorial algorithm; linear inequalities; network; gains

摘要

We give a simple primal algorithm for the generalized maximum flow problem that repeatedly finds and cancels generalized augmenting paths (GAPs). We use ideas of Wallacher (A generalization of the minimum-mean cycle selection rule in cycle canceling algorithms, 1991) to find GAPs that have a good trade-off between the gain of the GAP and the residual capacity of its arcs; our algorithm may be viewed as a special case of Wayne's algorithm for the generalized minimum-cost circulation problem (Wayne in Math Oper Res 27:445-459, 2002). Most previous algorithms for the generalized maximum flow problem are dual-based; the few previous primal algorithms (including Wayne in Math Oper Res 27: 445-459, 2002) require subroutines to test the feasibility of linear programs with two variables per inequality (TVPIs). We give an O(mn) time algorithm for finding negative-cost GAPs which can be used in place of the TVPI tester. This yields an algorithm with O(m log(mB/epsilon)) iterations of O(mn) time to compute an epsilon-optimal flow, or O(m(2) log(mB)) iterations to compute an optimal flow, for an overall running time of O(m(3)n log(mB)). The fastest known running time for this problem is (O) over tilde (m(2)n log B), and is due to Radzik (Theor Comput Sci 312:75-97, 2004), building on earlier work of Goldfarb et al. (Math Oper Res 22:793-802, 1997).