A cost-scaling algorithm for minimum-cost node-capacitated multiflow problem

• 成果类型: Article
• 署名作者: Hirai, Hiroshi; Ikeda, Motoki
• 署名单位: University of Tokyo
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-021-01683-6
• 发表日期: 2022
• 页码: 149-181
• 关键词: VECTORS

摘要

In this paper, we address the minimum-cost node-capacitated multiflow problem in undirected networks. For this problem, Babenko and Karzanov (JCO 24: 202-228, 2012) showed strong polynomial-time solvability via the ellipsoid method. Our result is the first combinatorial polynomial-time algorithm for this problem. Our algorithm finds a half-integral minimum-cost maximum multiflow in O(mlog(nCD)SF(kn,m,k)) time, where n is the number of nodes, m is the number of edges, k is the number of terminals, C is the maximum node capacity, D is the maximum edge cost, and SF(n',m',eta) is the time complexity of solving the submodular flow problem in a network of n' nodes, m' edges, and a submodular function with eta-time-computable exchange capacity. Our algorithm is built on discrete convex analysis on graph structures and the concept of reducible bisubmodular flows.