A Capacity Scaling Algorithm for the Constrained Maximum Flow Problem
Abstract
The constrained maximum flow problem is to send the maximum possible flow from a source node 5 to a sink node tin a directed network subject to a budget constraint that the cost of flow is no more than D. In this paper, we consider two versions of this problem: (i) when the cost of flow on each arc is a linear function of the amount of flow; and (ii) when the cost of flow is a convex function of the amount of flow. We suggest capacity scaling algorithms that solve both versions of the constrained maximum flow problem in o((m log M) s(n, m)) time, where n is the number of nodes in the network, m is the number of arcs, M is an upper bound on the largest element in the data, and s(n, m) is the time required to solve a shoflest path problem with nonnegative arc lengths. Our algorithms are modifications of the capacity scaling algorithms for the minimum cost flow and convex cost flow problems, and illustrate the power of capacity scaling algorithms to solve variants of the minimum cost flow problem in polynomial time.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jul 01, 1993
- Accession Number
- ADA459686
Entities
People
- I. I. Kanpur
- James B. Orlin
- Ravindra K. Ahuja
Organizations
- Massachusetts Institute of Technology