Half-integrality of node-capacitated multiflows and tree-shaped facility locations on trees

• 成果类型: Article
• 署名作者: Hirai, Hiroshi
• 署名单位: University of Tokyo
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-011-0506-7
• 发表日期: 2013
• 页码: 503-530
• 关键词: maximum number; minimum; algorithm; path

摘要

In this paper, we establish a novel duality relationship between node-capacitated multiflows and tree-shaped facility locations. We prove that the maximum value of a tree-distance-weighted maximum node-capacitated multiflow problem is equal to the minimum value of the problem of locating subtrees in a tree, and the maximum is attained by a half-integral multiflow. Utilizing this duality, we show that a half-integral optimal multiflow and an optimal location can be found in strongly polynomial time. These extend previously known results in the maximum free multiflow problems. We also show that the set of tree-distance weights is the only class having bounded fractionality in maximum node-capacitated multiflow problems.