The minimum cost flow problem: A unifying approach to dual algorithms and a new tree-search algorithm |
| |
Authors: | Refael Hassin |
| |
Affiliation: | (1) Statistics Department, Tel-Aviv University, Tel-Aviv, Israel |
| |
Abstract: | This paper is concerned with the minimum cost flow problem. It is shown that the class of dual algorithms which solve this problem consists of different variants of a common general algorithm. We develop a new variant which is, in fact, a new form of the ‘primal-dual algorithm’ and which has several interesting properties. It uses, explicitly only dual variables. The slope of the change in the (dual) objective is monotone. The bound on the maximum number of iterations to solve a problem with integral bounds on the flow is better than bounds for other algorithms. This paper is part of the author's doctoral dissertation submitted at Yale University. |
| |
Keywords: | Minimum Cost Network Flow Tree-Search Algorith Primal-Dual Algorithm |
本文献已被 SpringerLink 等数据库收录! |
|