Accession Number:

ADA459686

Title:

A Capacity Scaling Algorithm for the Constrained Maximum Flow Problem

Descriptive Note:

Corporate Author:

MASSACHUSETTS INST OF TECH CAMBRIDGE LAB FOR INFORMATION AND DECISION SYSTEMS

Report Date:

1993-07-01

Pagination or Media Count:

23.0

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 om log M sn, 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 sn, 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.

Subject Categories:

  • Numerical Mathematics
  • Computer Systems

Distribution Statement:

APPROVED FOR PUBLIC RELEASE