MINIMUM-COST FLOWS IN CONVEX-COST NETWORKS

Abstract

An algorithm is given for solving minimum-cost flow problems where the shipping cost over an arc is convex function of the number of units shipped along that arc. This provides a unified way of looking at many seemingly unrelated problems in different areas. In particular, it is shown how problems associated with electrical networks, with increasing the capacity of a network under a fixed budget, with Laplace equations, and with the Max-Flow Min-Cut Theorem may all be formulated into minimum-cost flow problems in convex-cost networks.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Mar 01, 1966
Accession Number
AD0636514

Entities

People

  • T. C. Hu

Organizations

  • University of California, Berkeley

Tags

DTIC Thesaurus Topics

  • Air Force
  • Algorithms
  • Boundaries
  • Boundary Value Problems
  • Communication Systems
  • Difference Equations
  • Electrical Networks
  • Equations
  • Military Research
  • Networks
  • Simultaneous Equations

Readers

  • Calculus or Mathematical Analysis
  • Graph Algorithms and Convex Optimization.
  • Industrial Economics