More Web Proxy on the site http://driver.im/

research-article

A fast algorithm for the generalized parametric minimum cut problem and applications

Authors:

Charles MartelAuthors Info & Claims

Algorithmica, Volume 7, Issue 1-6

Pages 499 - 519

https://doi.org/10.1007/BF01758775

Published: 01 June 1992 Publication History

Abstract

Many combinatorial optimization problems are solved by a sequence of network flow computations on a network whose edge capacities are given as a function of a parameter λ. Recently Galloet al. [7] made a major advance in solving such parametric flow problems. They showed that for an important class of networks, calledmonotone parametric flow networks, a sequence ofO(n) flow computations could be solved in the same worst-case time bound as a single flow. However, these results require one of two special assumptions: either that the λ values are presented in increasing or decreasing order; or that the edge capacity functions are affine functions of λ. In this paper we show how to remove both of these assumptions while obtaining the same running times as in [7]. This observation generalizes and unifies the two major results of [7], and allows its ideas to be applied to many new combinatorial problems. Of greatest importance, it allows the efficient application of binary search and successive binary search to a sequence of network flow problems.

References

[1]

R. Ahuja, J. Orlin, C. Stein, and R. E. Tarjan. Improved algorithms for bipartite network flow. Unpublished manuscript, 1989.

[2]

Cheung T. Y. Multifacility location problem with rectilinear distance by the minimum-cut approach ACM Transactions on Mathematical Software 1980 6 549-561

[3]

W. H. Cunningham. Computing the binding number of a graph. Manuscript, July 1988.

[4]

Eisner M. and Severance D. Mathematical techniques for efficient record segmentation in large shared databases Journal of the Association for Computing Machinery 1976 23 619-635

[5]

Ford L. R. and Fulkerson D. R. Flows in Networks 1962 Princeton, NJ Princeton University Press

[6]

Gale D. and Shapley L. S. College admissions and the stability of marriage American Mathematical Monthly 1962 69 9-15

[7]

Gallo G., Grigoriadis M., and Tarjan R. E. A fast parametric network flow algorithm SIAM Journal on Computing 1989 18 30-55

[8]

Goldberg A. and Tarjan R. E. A new approach to the maximum flow problem Journal of the Association for Computing Machinary 1988 4 136-146

[9]

Gusfield D. A Faster Parametric Minimum Cut Algorithm 1990 Davis Computer Science Division, University of California

[10]

Gusfield D. and Irving R. The Stable Marriage Problem: Structure and Algorithms 1989 Cambridge, MA MIT Press

[11]

Hoffman A. and Rivlin J. Kuhn H. W. When is a team “mathematically” eliminated? Princeton Symposium on Math Programming (1967) 1970 Princeton, NJ Princeton University Press 391-401

[12]

Irving R. W. and Leather P. The complexity of counting stable marriages SIAM Journal on Computing 1986 15 655-667

[13]

Irving R. W., Leather P., and Gusfield D. An efficient algorithm for the “optimal” stable marriage Journal of the Association for Computing Machinery 1987 34 532-543

[14]

Knuth D. E. Marriages Stables 1976 Montreal Les Presses de l'Université de Montréal

[15]

Lawler E. L. Combinatorial Optimization: Networks and Matroids 1976 New York Holt, Rinehart and Winston

[16]

Picard J. and Ratliff H. A cut approach to the rectilinear distance facility location problem Operations Research 1978 26 422-433

[17]

Polyá G., Tarjan R. E., and Woods D. R. Notes on Introductory Combinatorics 1983 Basel Birkhäuser-Verlag

[18]

Schwartz B. Possible winners in partially completed tournaments SIAM Review 1966 8 302-308

[19]

C. Stein. Efficient algorithms for bipartite network flow. Unpublished manuscript, Princeton University, 1987.

[20]

Stone H. S. Critical load factors in two-processor distributed systems IEEE Transactions on Software Engineering 1978 3 254-258

[21]

G. Sullivan. Personal communication.

[22]

Tarjan R. E. Data Structures and Network Algorithms 1983 Philadelphia, PA SIAM

[23]

Trubin V. A. Effective algorithm for the weber problem with a rectangular metric Cybernetics 1978 14 874-878

Cited By

Leung GQuadrianto NSmola ATsioutsiouliklis K(2010)Optimal web-scale tiering as a flow problemProceedings of the 24th International Conference on Neural Information Processing Systems - Volume 110.5555/2997189.2997338(1333-1341)Online publication date: 6-Dec-2010
https://dl.acm.org/doi/10.5555/2997189.2997338

Recommendations

A faster parametric minimum-cut algorithm

Galloet al. [4] recently examined the problem of computing on line a sequence ofk maximum flows and minimum cuts in a network ofn nodes, where certain edge capacities change between each flow. They showed that for an important class of networks, thek ...
Parametric multiroute flow and its application to multilink-attack network

We investigate variants of the max-flow problem in a network under k attacks. The network interdiction problem is to find the minimum max-flow value among (mk) networks that can be obtained by deleting each set of k links. The adaptive network flow ...
Improved balanced flow computation using parametric flow

We present a new algorithm for computing balanced flows in equality networks arising in market equilibrium computations. The current best time bound for computing balanced flows in such networks requires O ( n ) maxflow computations, where n is the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Algorithmica

Algorithmica Volume 7, Issue 1-6

Jun 1992

628 pages

ISSN:0178-4617

Issue’s Table of Contents

© Springer-Verlag New York Inc. 1992.

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 01 June 1992

Revision received: 07 June 1990

Received: 18 August 1988

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 07 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Leung GQuadrianto NSmola ATsioutsiouliklis K(2010)Optimal web-scale tiering as a flow problemProceedings of the 24th International Conference on Neural Information Processing Systems - Volume 110.5555/2997189.2997338(1333-1341)Online publication date: 6-Dec-2010
https://dl.acm.org/doi/10.5555/2997189.2997338

View Options

View options

Figures

Tables

Media

View Issue’s Table of Contents