A polynomial combinatorial algorithm for generalized minimum cost flow

Research output: Contribution to journalArticle

31 Scopus citations

Abstract

We propose the first combinatorial solution to the generalized minimum cost flow problem (flow with losses and gains). Despite a rich history dating back to Kantorovich and Dantzig, until now, the only known way to solve the problem in polynomial-time was via general-purpose linear programming techniques. Polynomial combinatorial algorithms were previously known only for the version of our problem without costs. We design the first such algorithms for the version with costs. Our algorithms also find provably good solutions faster than optimal ones, providing the first strongly polynomial approximation schemes for the problem. Our techniques extend to optimize linear programs with two variables per inequality. Polynomial combinatorial algorithms were previously developed for testing the feasibility of such linear programs. We propose the first such methods for the optimization version.

Original languageEnglish (US)
Pages (from-to)445-459
Number of pages15
JournalMathematics of Operations Research
Volume27
Issue number3
DOIs
StatePublished - Aug 2002

All Science Journal Classification (ASJC) codes

  • Mathematics(all)
  • Computer Science Applications
  • Management Science and Operations Research

Keywords

  • Gain factor
  • Generalized minimum cost flow
  • Minimum cost flow
  • Polynomial combinatorial algorithm
  • Strongly polynomial approximation scheme

Fingerprint Dive into the research topics of 'A polynomial combinatorial algorithm for generalized minimum cost flow'. Together they form a unique fingerprint.

  • Cite this