Name
Abstract | ||
|---|---|---|
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/ε)) iterations of O(mn) time to compute an ε-optimal flow, or O(m 2 log (mB)) iterations to compute an optimal flow, for an overall running time of O(m 3 nlog(mB)). The fastest known running time for this problem is $$\tilde{O}(m^2n\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). |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1007/s10107-007-0183-8 | Symposium on Discrete Algorithms |
Keywords | Field | DocType |
simple primal algorithm,m log,negative-cost gaps,generalized maximum flow problem,optimal flow,simple gap-canceling algorithm,math oper res,time algorithm,previous algorithm,previous primal algorithm,generalized minimum-cost circulation problem,linear program,maximum flow | Subroutine,Circulation problem,Maximum flow problem,Linear programming,Graph theory,Flow network,Discrete mathematics,Combinatorics,Mathematical optimization,Algorithm,Cycle graph,Mathematics,Computational complexity theory | Journal |
Volume | Issue | ISSN |
118 | 1 | 1436-4646 |
ISBN | Citations | PageRank |
0-89871-605-5 | 5 | 0.43 |
References | Authors | |
21 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Mateo Restrepo | 1 | 56 | 2.42 |
| David P. Williamson | 2 | 3564 | 413.34 |