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.

• 社団法人電子情報通信学会の論文
• 2010-04-15

著者

• Hirai Hiroshi

  Research Institute For Mathematical Sciences Kyoto University

関連論文

• A NOTE ON MULTIFLOW LOCKING THEOREM
• M-Convex Functions and Tree Metrics
• Half-integrality of node-capacitated multiflows and tree-shaped facility locations on trees (コンピュテーション)

スポンサーリンク