TY - GEN
T1 - Experimental evaluation of parametric max-flow algorithms
AU - Babenko, Maxim
AU - Derryberry, Jonathan
AU - Goldberg, Andrew
AU - Tarjan, Robert
AU - Zhou, Yunhong
PY - 2007
Y1 - 2007
N2 - The parametric maximum flow problem is an extension of the classical maximum flow problem in which the capacities of certain arcs are not fixed but are functions of a single parameter. Gallo et al. [6] showed that certain versions of the push-relabel algorithm for ordinary maximum flow can be extended to the parametric problem while only increasing the worst-case time bound by a constant factor. Recently Zhang et al. [14,13] proposed a novel, simple balancing algorithm for the parametric problem on bipartite networks. They claimed good performance for their algorithm on networks arising from a real-world application. We describe the results of an experimental study comparing the performance of the balancing algorithm, the GGT algorithm, and a simplified version of the GGT algorithm, on networks related to those of the application of Zhang et al. as well as networks designed to be hard for the balancing algorithm. Our implementation of the balancing algorithm beats both versions of the GGT algorithm on networks related to the application, thus supporting the observations of Zhang et al. On the other hand, the GGT algorithm is more robust; it beats the balancing algorithm on some natural networks, and by asymptotically increasing amount on networks designed to be hard for the balancing algorithm.
AB - The parametric maximum flow problem is an extension of the classical maximum flow problem in which the capacities of certain arcs are not fixed but are functions of a single parameter. Gallo et al. [6] showed that certain versions of the push-relabel algorithm for ordinary maximum flow can be extended to the parametric problem while only increasing the worst-case time bound by a constant factor. Recently Zhang et al. [14,13] proposed a novel, simple balancing algorithm for the parametric problem on bipartite networks. They claimed good performance for their algorithm on networks arising from a real-world application. We describe the results of an experimental study comparing the performance of the balancing algorithm, the GGT algorithm, and a simplified version of the GGT algorithm, on networks related to those of the application of Zhang et al. as well as networks designed to be hard for the balancing algorithm. Our implementation of the balancing algorithm beats both versions of the GGT algorithm on networks related to the application, thus supporting the observations of Zhang et al. On the other hand, the GGT algorithm is more robust; it beats the balancing algorithm on some natural networks, and by asymptotically increasing amount on networks designed to be hard for the balancing algorithm.
UR - http://www.scopus.com/inward/record.url?scp=37149016117&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=37149016117&partnerID=8YFLogxK
U2 - 10.1007/978-3-540-72845-0_20
DO - 10.1007/978-3-540-72845-0_20
M3 - Conference contribution
AN - SCOPUS:37149016117
SN - 3540728449
SN - 9783540728443
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 256
EP - 269
BT - Experimental Algorithms - 6th International Workshop, WEA 2007, Proceedings
PB - Springer Verlag
T2 - 6th International Workshop on Experimental Algorithms, WEA 2007
Y2 - 6 June 2007 through 8 June 2007
ER -