As fast parametric maximum flow algorithm and applications

As fast parametric maximum flow algorithm and applications

0.00 Avg rating0 Votes
Article ID: iaor19881237
Country: United States
Volume: 18
Issue: 1
Start Page Number: 30
End Page Number: 55
Publication Date: Feb 1989
Journal: SIAM Journal On Control and Optimization
Authors: , ,
Keywords: combinatorial analysis, networks, programming: parametric
Abstract:

The classical maximum flow problem sometimes occurs in settings in which the arc capacities are not fixed but are functions of a single parameter, and the goal is to find the value of the parameter such that the corresponding maximum flow or minimum cut satisfies some side condition, Finding the desired parameter value requires solving a sequence of related maximum flow problems. In this paper it is shown that the recent maximum flow algorithm of Goldberg and Tarjan can be extended to solve an important class of such parametric maximum flow problems, at the cost of only a constant factor in its worst-case time bound. Faster algorithms for a variety of combinatorial optimization problems follow from the result.

Reviews

Required fields are marked *. Your email address will not be published.