Theory and algorithm of multiflow, facility location, and network design

多流、设施选址和网络设计的理论和算法

• 批准号: 23740068
• 负责人: HIRAI Hiroshi
• 金额: $ 1.41万
• 依托单位: The University of Tokyo
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Young Scientists (B)
• 财政年份: 2011
• 资助国家: 日本
• 起止时间: 2011 至 2013
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-23740068/
• 关键词: 施設配置問題; 多品種流; ネットワークデザイン; メトリック; 劣モジュラ関数; 離散凸関数

The main result of this research project is to complete the classification of graphs G for which multifacility location problem (minimum 0-extension problem) on G is polynomial time solvable. In the proof, we introduced discrete convex functions on a class of graphs, and opened up new research direction "discrete convexity for multiflow and facility locations." This is an important step toward a unified theory for multiflow, facility location, and network design, which was the goal of this research project.

本课题的主要成果是完成图G的分类，其中G上的多设施定位问题（最小0-扩展问题）是多项式时间可解的。在证明中，我们在一类图上引入离散凸函数，开辟了“多流和设施位置的离散凸性”这一新的研究方向。这是向多流、设施选址和网络设计的统一理论迈出的重要一步，也是本研究项目的目标。

项目成果

0n tight spans for directed distances

定向距离的 0n 紧密跨度

• 发表时间: 2012
• 期刊: Annals of Combinatorics
• 影响因子: 0.5
• 作者: Yata;K.;Aoshima;M.;斉木吉隆;矢田和善，青嶋 誠;Hiroshi Hirai and Shungo Koichi
• 通讯作者: Hiroshi Hirai and Shungo Koichi

Discrete convexity for multiflows and 0-extensions

多流和 0 扩展的离散凸性

• 发表时间: 2013
• 作者: T. KUBO;T. IWASATO;Y. YOSHIDA; Y. HIGO;T. KATO;H. Hirai
• 通讯作者: H. Hirai

Discrete convexity and polynomial solvability in minimum 0-extension problems

• DOI: 10.1007/s10107-014-0824-7
• 发表时间: 2013-01
• 期刊: Mathematical Programming
• 影响因子: 2.7
• 作者: H. Hirai

Weight classication in multiflow problems

多流问题中的权重分类

• 发表时间: 2011
• 作者: K. Yata;M. Aoshima;中野張;Yoshitaka Saiki;H. Hirai;Y. Nakano;K. Yata;H. Hirai
• 通讯作者: H. Hirai

Bounded fractionality of the multiflow feasibility problem for demand graph K_3 + K_3 and related maximization problems

需求图K_3 K_3多流可行性问题的有界分数及相关最大化问题

• DOI: 10.1016/j.jctb.2012.02.001
• 发表时间: 2012
• 期刊: Journal of Combinatorial Theory,Series B
• 作者: 矢田和善;青嶋 誠;Y. Saiki;H. Hirai
• 通讯作者: H. Hirai