Relaxed most negative cycle and most positive cut canceling algorithms for minimum cost flow

• 成果类型: Article
• 署名作者: Shigeno, M; Iwata, S; McCormick, ST
• 署名单位: University of Tsukuba; University of Osaka; University of British Columbia
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.25.1.76.15208
• 发表日期: 2000
• 页码: 76-104
• 关键词: network simplex algorithm; circulation algorithm; scaling algorithms; dynamic trees; mean cuts; optimization; bounds

摘要

This paper presents two new scaling algorithms for the minimum cost network flow problem, one a primal cycle canceling algorithm, the other a dual cut canceling algorithm. Both algorithms scale a relaxed optimality parameter, and create a second, inner relaxation. The primal algorithm uses the inner relaxation to cancel a most negative node-disjoint Family of cycles w.r.t. the scaled parameter, the dual algorithm uses it to cancel most positive cuts w.r.t. the scaled parameter. We show that in a network with n nodes and m area, both algorithms need to cancel only O(mn) objects per scaling phase. Furthermore, we show how to efficiently implement both algorithms to yield weakly polynomial running times that are as fast as any other cycle or cut canceling algorithms. Our algorithms have potential practical advantages compared to some other canceling algorithms as well. Along the way, we give a comprehensive survey of cycle and cut canceling algorithms for min-cost flow. We also clarify the formal duality between cycles and cuts.