Combinatorial Algorithms for the Generalized Circulation Problem

Abstract

We consider a generalization of the maximum network flow problem in which the amounts of flow entering and leaving an arc are linearly related. More precisely, if x(e) units of flow enter an arc e, x(e) gamma (e) units arrive at the other end. For instance, nodes of the graph can correspond to different currencies, with the multipliers being the exchange rates. We require conservation of flow at every node except a given source node. The goal is to maximize the amount of flow excess at the source. This problem is a special case of linear programming, and therefore can be solved in polynomial time. In this paper we present the first polynomial time combinatorial optimization algorithms for this problem. The algorithms are simple and intuitive.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
May 01, 1988
Accession Number
ADA197409

Entities

People

  • Andrew V. Goldberg
  • Serge A. Plotkin
  • Éva Tardos

Organizations

  • Massachusetts Institute of Technology

Tags

DTIC Thesaurus Topics

  • Algorithms
  • Applied Mathematics
  • Classification
  • Computations
  • Computer Science
  • Computers
  • Evolutionary Algorithms
  • Flow Network
  • Information Processing
  • Linear Programming
  • Mathematics
  • Numbers
  • Operations Research
  • Optimization
  • Real Numbers
  • Simplex Method
  • Trees (Data Structures)

Readers

  • Combustion and Flow Dynamics.
  • Operations Research