Canceling most helpful total cuts for minimum cost network flow
作者:
Thomas R. Ervolina,
S. Thomas McCormick,
期刊:
Networks
(WILEY Available online 1993)
卷期:
Volume 23,
issue 1
页码: 41-52
ISSN:0028-3045
年代: 1993
DOI:10.1002/net.3230230106
出版商: Wiley Subscription Services, Inc., A Wiley Company
数据来源: WILEY
摘要:
AbstractWe present a polynomial algorithm for the minimum cost network flow problem (MCNF). It is a dual algorithm that is based on canceling positive augmenting cuts, which are the duals of negative augmenting cycles. We focus on cancelingmost helpful total cuts, which are cuts together with augmentation amounts that lead to the maximum possible increase in the dual objective function. We show how to compute a most helpful total cut and give a rigorous dual conformal decomposition theorem. Canceling most helpful cuts is, in spirit, dual to an algorithm of Weintraub as modified by Barahona and Tardos. We also show how our algorithm specializes to the case of shortests–tpath with nonnegative distances, show that this specialization is not finite for real data, and show that our bound on the number of cancellations is essentially tight. ©1993 by John Wiley&Sons, I
点击下载:
PDF
(875KB)
返 回