Finding Minimum-Cost Circulations by Canceling Negative Cycles.

Abstract

A classical algorithm for finding a minimum cost circulation consists of repeatedly finding a residual cycle of negative cost and canceling it by pushing enough flow around the cycle to saturate an arc. We show that a judicious choice of cycles for canceling leads to a polynomial bound on the number of iterations in this algorithm. This gives a very simple strongly polynomial algorithm that uses no scaling. A variant of the algorithm that uses dynamic trees runs in 0(nm(log n)min(log(nC), mlogn)) time on a network of n vertices, m arcs, and arc costs of maximum absolute value C. This bound is comparable to those of the fastest previously known algorithms. Keywords: Network flows, Minimum cost flow, Combinatorial optimization.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jul 01, 1987
Accession Number
ADA192727

Entities

People

  • Andrew V. Goldberg
  • Robert Tarjan

Organizations

  • Massachusetts Institute of Technology

Tags

Communities of Interest

  • Weapons Technologies

DTIC Thesaurus Topics

  • Algorithms
  • Cancellation
  • Classification
  • Computations
  • Computer Science
  • Computers
  • Department Of Defense
  • Information Processing
  • Information Systems
  • Iterations
  • Linear Programming
  • Military Research
  • New Jersey
  • Numbers
  • Polynomials
  • Security
  • Standards

Readers

  • Economics
  • Graph Algorithms and Convex Optimization.