Polynomial combinatorial algorithm for generalized minimum cost flow

Research output: Contribution to journalConference article

22 Scopus citations

Abstract

We develop the first polynomial combinatorial algorithm for generalized minimum cost flow. 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 ellipsoid or interior point methods. Flow-based polynomial algorithms were previously known only for the version of our problem without costs. We design the first flow-based polynomial algorithms for the version with costs. We can also find provably good solutions faster than optimal ones. We obtain the first strongly polynomial approximation schemes for generalized network flow with costs. Our techniques also extend to optimize linear programs with two variables per inequality. Polynomial combinatorial algorithms were previously developed for testing the feasibility of such linear programs. Until now, no such methods were known for the optimization version.

Original languageEnglish (US)
Pages (from-to)11-18
Number of pages8
JournalConference Proceedings of the Annual ACM Symposium on Theory of Computing
StatePublished - Jan 1 1999
EventProceedings of the 1999 31st Annual ACM Symposium on Theory of Computing - FCRC '99 - Atlanta, GA, USA
Duration: May 1 1999May 4 1999

All Science Journal Classification (ASJC) codes

  • Software

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

Cite this