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

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. [ABSTRACT FROM AUTHOR]