首页 | 本学科首页   官方微博 | 高级检索  
     检索      


The minimum cost flow problem: A unifying approach to dual algorithms and a new tree-search algorithm
Authors:Refael Hassin
Institution:(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 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号