Epsilon-relaxation and auction algorithms for the convex cost network flow problem
Lazaros Polymenakos, Dimitri P. Bertsekas · 1995
The problem considered is the convex cost network flow problem; we propose auction and $\epsilon$-relaxation algorithms for its solution. These methods stem from the $\epsilon$-relaxation and auction algorithms that have already been developed for the linear cost problem. The new methods operate by doing an approximate coordinate ascent, where neither the primal nor the dual cost necessarily improves in a particular iteration. What motivates these methods is their good performance for the linear programming case. Our analysis shows that the $\epsilon$-relaxation and auction methods for the convex cost problem have polynomial complexity, making them attractive for practical applications. Computational experimentation verifies this claim. (Copies available exclusively from MIT Libraries, Rm. 14-0551, Cambridge, MA 02139-4307. Ph. 617-253-5668; Fax 617-253-1690.)