Accession Number:

ADA214498

Title:

Finding Minimum-Cost Flows by Double Scaling

Descriptive Note:

Corporate Author:

PRINCETON UNIV NJ DEPT OF COMPUTER SCIENCE

Report Date:

1988-06-01

Pagination or Media Count:

31.0

Abstract:

Several researchers have recently developed new techniques that give fast algorithms for the minimum-cost flow problem. In this paper we combine several of these techniques to yield an algorithm running in Onm log log UnC time on networks with n vertices, m arcs, maximum arc capacity U, and maximum arc cost magnitude C. The major techniques used are the capacity-scaling approach of Edmonds and Karp, the excess-scaling approach of Ahuja and Orlin, the cost-scaling approach of Goldberg and Tarjan, and the dynamic tree data structure of Sleator and Tarjan. For nonsparse graphs with large maximum arc capacity, we obtain a similar but slightly better bound. We also obtain a slightly better bound for the uncapacitated transportation problem. In addition, we discuss a capacity-bounding approach to the minimum cost flow problem.

Subject Categories:

  • Economics and Cost Analysis
  • Operations Research

Distribution Statement:

APPROVED FOR PUBLIC RELEASE