Presentation	2010-04-22 Half-integrality of node-capacitated multiflows and tree-shaped facility locations on trees Hiroshi Hirai,
PDF Download Page	PDF download Page Link
Abstract(in Japanese)	(See Japanese page)
Abstract(in English)	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.
Keyword(in Japanese)	(See Japanese page)
Keyword(in English)	Multicommodity flows / tree-shaped facility locations / polynomial time algorithm
Paper #	COMP2010-9
Date of Issue

Conference Information
Committee	COMP
Conference Date	2010/4/15(1days)
Place (in Japanese)	(See Japanese page)
Place (in English)
Topics (in Japanese)	(See Japanese page)
Topics (in English)
Chair
Vice Chair
Secretary
Assistant

Paper Information
Registration To	Theoretical Foundations of Computing (COMP)
Language	ENG
Title (in Japanese)	(See Japanese page)
Sub Title (in Japanese)	(See Japanese page)
Title (in English)	Half-integrality of node-capacitated multiflows and tree-shaped facility locations on trees
Sub Title (in English)
Keyword(1)	Multicommodity flows
Keyword(2)	tree-shaped facility locations
Keyword(3)	polynomial time algorithm
1st Author's Name	Hiroshi Hirai
1st Author's Affiliation	Research Institute for Mathematical Sciences, Kyoto University()
Date	2010-04-22
Paper #	COMP2010-9
Volume (vol)	vol.110
Number (no)	12
Page	pp.pp.-
#Pages	8
Date of Issue