A capacity scaling algorithm for M-convex submodular flow

• 成果类型: Article
• 署名作者: Iwata, S; Moriguchi, S; Murota, K
• 署名单位: University of Tokyo
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-004-0562-3
• 发表日期: 2005
• 页码: 181-202
• 关键词: valuated matroid intersection

摘要

This paper presents a faster algorithm for the M-convex submodular flow problem, which is a generalization of the minimum-cost flow problem with an M-convex cost function for the flow-boundary, where an M-convex function is a nonlinear nonseparable discrete convex function on integer points. The algorithm extends the capacity scaling approach for the submodular flow problem by Fleischer, Iwata and McCormick (2002) with the aid of a novel technique of changing the potential by solving maximum submodular flow problems.