The Maximum Multiflow Problems with Bounded Fractionality

• 成果类型: Article
• 署名作者: Hirai, Hiroshi
• 署名单位: University of Tokyo
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2013.0600
• 发表日期: 2014
• 页码: 60-104
• 关键词: COMBINATORIAL; algorithm

摘要

We consider the weighted maximum multiflow problem with respect to a terminal weight. We show that if the dimension of the tight span associated with the weight is at most 2, then this problem has a 1/12-integral optimal multiflow for every Eulerian supply graph. This result solves a weighted generalization of Karzanov's conjecture for classifying commodity graphs with finite fractionality. In addition, our proof technique proves the existence of an integral or half-integrality optimal multiflow for a large class of multiflow maximization problems, and it gives a polynomial time algorithm.