A Strongly Polynomial Algorithm for Generalized Flow Maximization

• 成果类型: Article
• 署名作者: Vegh, Laszlo A.
• 署名单位: University of London; London School Economics & Political Science
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2016.0800
• 发表日期: 2017
• 页码: 179-211
• 关键词: minimum-cost flow; circulation problem; linear-programs; Combinatorial algorithm; network; gains

摘要

A strongly polynomial algorithm is given for the generalized flow maximization problem. It uses a new variant of the scaling technique called continuous scaling. The main measure of progress is that within a strongly polynomial number of steps, an arc can be identified that must be tight in every dual optimal solution and thus can be contracted. As a consequence of the result, we also obtain a strongly polynomial algorithm for the linear feasibility problem with at most two nonzero entries per column in the constraint matrix.