Princeton COS 521 - Beyond the Flow Decomposition Barrier

Unformatted text preview:

Beyond the Flow Decomposition BarrierANDREW V. GOLDBERG AND SATISH RAONEC Research Institute, Princeton, New JerseyAbstract. We introduce a new approach to the maximum flow problem. This approach is based onassigning arc lengths based on the residual flow value and the residual arc capacities. Our approachleads to an O(min(n2/3, m1/2)m log(n2/m) log U) time bound for a network with n vertices, m arcs,and integral arc capacities in the range [1, . . . , U]. This is a fundamental improvement over theprevious time bounds. We also improve bounds for the Gomory–Hu tree problem, the parametricflow problem, and the approximate s-t cut problem.Categories and Subject Descriptors: F.2.2, [Analysis of Algorithms and Problem Complexity]:Nonnumerical Algorithms and Problems; G.2.2 [Discrete Mathematics]: Graph TheoryGeneral Terms: AlgorithmsAdditional Key Words and Phrases: Combinatorial optimization, maximum flows1. IntroductionThe maximum flow problem and its dual, the minimum cut problem, are classicalcombinatorial problems with a wide variety of scientific and engineering applica-tions. The maximum flow problem and related flow and cut problems have beenstudied intensively for over three decades.The network simplex method of Dantzig [1951] for the transportation problemsolves the maximum flow problem as a natural special case. Soon thereafter,Ford and Fulkerson [1956] developed the augmenting path method for themaximum flow problem. A natural variant of this method, the shortest augment-ing path algorithm, was shown to be polynomial by Dinitz [1970] and Edmondsand Karp [1972]. Capacity scaling, developed by Edmonds and Karp [1972] andDinitz [1973], also gives polynomial algorithms for the problem. (See also Gabow[1985].) Classical books [Adel’son-Vel’ski et al. 1975; Ford and Fulkerson 1962]describe earlier work in detail.Most efficient algorithms for the maximum flow problem are based on theblocking flow and the push-relabel methods. The first blocking flow algorithmwas developed by Dinitz [1970] in the framework of the augmenting pathapproach. Karzanov [1974] was the first to state the finding of a blocking flow asAuthors’ address: NEC Research Institute, 4 Independence Drive, Princeton, NJ 08540; e-mail: [avg,satish]@research.nj.nec.com.Permission to make digital/hard copy of part or all of this work for personal or classroom use isgranted without fee provided that the copies are not made or distributed for profit or commercialadvantage, the copyright notice, the title of the publication, and its date appear, and notice is giventhat copying is by permission of the Association for Computing Machinery (ACM), Inc. To copyotherwise, to republish, to post on servers, or to redistribute to lists, requires prior specific permissionand/or a fee.© 1998 ACM 0004-5411/98/0900-0783 $05.00Journal of the ACM, Vol. 45, No. 5, September 1998, pp. 783–797.a separate problem and to suggest the use of preflows to solve it. Thepush-relabel method, implicit in Goldberg’s algorithm [1985], was fully devel-oped by Goldberg and Tarjan [1988].The shortest augmenting path algorithm, the blocking flow method, and thepush-relabel method use a concept of distance. To talk about distances, one hasto define arc lengths. All these approaches use the unit length function: thelength of every residual arc is defined to be one. Edmonds and Karp [1972]discussed the use of general length functions in the context of maximum flows.Wallacher and Zimmermann [1991] and Wallacher [1991] study length functionsin the context of the minimum-cost flow problem. However, prior to our work,the bounds obtained using general length functions were no better than thebounds using the unit length function.In this paper, we extend the blocking flow method to more general lengthfunctions and obtain substationally better time bounds. We study a binary lengthfunction that assigns zero length to large capacity arcs and unit length to smallcapacity arcs. A novel feature of our length function is that it is adaptive:wedefine the length threshold relative to an estimate on the residual flow value.Adaptivity is crucial for the time bound improvements.Table I gives the history of the maximum flow time bounds. We denote thenumber of vertices in the input network by n and the number of arcs by m. Forpolynomial algorithms, we assume that arc capacities are integers in the range[1, . . . , U]. Strongly polynomial algorithms do not need this assumption. Weuse the similarity assumption of Gabow [1985], log U 5 O(log n), to comparepolynomial and strongly polynomial algorithms. By a ballpark bound we mean anO* bound under the similarity assumption.1For a randomized algorithm runningin O(t) expected time, we denote its running time by E(t).The V(nm) bound is a natural barrier for maximum flow algorithms. In a pathdecomposition of a flow, the total path length is Q(nm) in the worst case. Thisimplies an V(nm) lower bound on algorithms which output explicit flowdecomposition and on algorithms which augment flow one path at a time and, foreach augmenting path, one arc at a time. This lower bound does not apply toalgorithms that work with preflows or use data structures like dynamic trees[Sleator and Tarjan 1983] to manipulate flows. However, in spite of numerousattempts, no previous algorithm achieves this lower bound in general. For densegraphs, the O(n3/log n) algorithm of Cheriyan et al. [1990] beats this lowerbound, but only by using word operations on (log n)-bit integers. The ballparkbound of nm was achieved by Dinitz [1973].In the unit capacity case, the total decomposition path length is O(m) ando(nm) bounds have been known for a long time: Karzanov [1973] and indepen-dently Even and Tarjan [1975] have shown that Dinitz’s algorithm [Dinic 1970]runs in O(min(n2/3, m1/2)m) time on unit capacity networks with no parallelarcs. (We define L5min(n2/3, m1/2); this term will appear quite often.) Thisbound is based on the O(L) bound on the number of blocking flow computationsof Dinitz’s algorithm on such networks. This result suggests a possibility of ano(nm) bound for general networks. However, for over two decades, no algorithmimproved upon the nm ballpark bound.1O*( f(n)) 5 O((log n)O(1)f(n)).784 A.V. GOLDBERG AND S. RAOWe achieve a Lm ballpark bound for general networks. Each iteration of ouralgorithm is dominated by a blocking flow computation on an acyclic graph.Using the blocking flow algorithm of Goldberg and Tarjan [1988], we get anO(Lm


View Full Document

Princeton COS 521 - Beyond the Flow Decomposition Barrier

Download Beyond the Flow Decomposition Barrier
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Beyond the Flow Decomposition Barrier and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Beyond the Flow Decomposition Barrier 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?