An ∈-relaxation method for separable convex cost network flow problems

Dimitri P. Bertsekas, Lazaros C. Polymenakos, Paul Tseng

Research output: Contribution to journalArticlepeer-review

20 Scopus citations


We propose a new method for the solution of the single commodity, separable convex cost network flow problem. The method generalizes the ∈-relaxation method developed for linear cost problems and reduces to that method when applied to linear cost problems. We show that the method terminates with a near optimal solution, and we provide an associated complexity analysis. We also present computational results showing that the method is much faster than earlier relaxation methods, particularly for ill-conditioned problems.

Original languageEnglish (US)
Pages (from-to)853-870
Number of pages18
JournalSIAM Journal on Optimization
Issue number3
StatePublished - Aug 1997
Externally publishedYes


  • Network flows
  • Network optimization
  • ∈-relaxation

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science


Dive into the research topics of 'An ∈-relaxation method for separable convex cost network flow problems'. Together they form a unique fingerprint.

Cite this