Multiflows and metrics

多流和指标

• 批准号: 20740054
• 负责人: HIRAI Hiroshi
• 金额: $ 1.33万
• 依托单位: Kyoto University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Young Scientists (B)
• 财政年份: 2008
• 资助国家: 日本
• 起止时间: 2008 至 2010
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-20740054/
• 关键词: マルチフロー; メトリック; ネットワークフロー; 最大最小定理; 多項式時間アルゴリズム

We studied multiflow problems in combinatorial optimization. We introduced and developed the tight-span duality theory, which extends the duality relationship between multiflows and metrics, a well-known duality since 70's. As a consequence, We solved Karzanov' s problem, one of important open problems in the literature, which asks a complete characterization for the class of multiflow problems admitting combinatorial min-max theorems and the discreteness of flows. This result is an important step toward a unified theory for multiflow problems.

我们研究了组合优化中的多流问题。我们引入并发展了紧跨对偶理论，该理论扩展了多流和度量之间的对偶关系，这是自 70 年代以来众所周知的对偶关系。因此，我们解决了卡尔扎诺夫问题，这是文献中重要的开放问题之一，它要求对承认组合最小-最大定理和流的离散性的多流问题进行完整的表征。这一结果是迈向多流问题统一理论的重要一步。

项目成果

Metric packing for K_3+K_3

K_3 的公制包装 K_3

• 发表时间: 2010
• 期刊: Combinatorica (掲載確定)
• 作者: Nobuhiro Asai;Nobuhiro ASAI;Nobuhiro Asai;Hiroshi Hirai;Nobuhiro ASAI;Hiroshi Hirai;Nobuhiro Asai;Nobuhiro Asai;Hiroshi Hirai;Nobuhiro Asai;Hiroshi Hirai;Nobuhiro ASAI;Hiroshi Hirai;Nobuhiro Asai;Hiroshi Hirai;Nobuhiro Asai;Hiroshi Hirai
• 通讯作者: Hiroshi Hirai

T_X-approaches to multiflows and metrics

T_X 多流和指标方法

• 发表时间: 2010
• 期刊: RIMS Kokyrurok Bessatsu
• 作者: Nobuhiro Asai;Nobuhiro ASAI;Nobuhiro Asai;Hiroshi Hirai;Nobuhiro ASAI;Hiroshi Hirai;Nobuhiro Asai;Nobuhiro Asai;Hiroshi Hirai;Nobuhiro Asai;Hiroshi Hirai;Nobuhiro ASAI;Hiroshi Hirai;Nobuhiro Asai;Hiroshi Hirai
• 通讯作者: Hiroshi Hirai

Bounded fractionality of multiflow feasibility problem for demand graph K3+K3 and other maximization problems

需求图 K3 K3 和其他最大化问题的多流可行性问题的有界分数

• 发表时间: 2009
• 作者: Nobuhiro Asai;Nobuhiro ASAI;Nobuhiro Asai;Hiroshi Hirai;Nobuhiro ASAI;Hiroshi Hirai;Nobuhiro Asai;Nobuhiro Asai;Hiroshi Hirai;Nobuhiro Asai;Hiroshi Hirai;Nobuhiro ASAI;Hiroshi Hirai;Nobuhiro Asai;Hiroshi Hirai;Nobuhiro Asai;Hiroshi Hirai;Nobuhiro Asai;Nobuhiro Asai;Hiroshi Hirai;Nobuhiro Asai;Hiroshi Hirai;Nobuhiro ASAI;Nobuhiro ASAI;Hiroshi Hirai;Nobuhiro ASAI;Hiroshi Hirai;Nobuhiro ASAI;Hiroshi Hirai;Nobuhiro ASAI;Nobuhiro Asai;平井広志;Nobuhiro Asai;Hiroshi Hirai;Nobuhiro Asai;Nobuhiro Asai;Hiroshi Hirai;Nobuhiro ASAI;Hiroshi Hirai;平井広志;Nobuhiro ASAI;平井広志;Nobuhiro ASAI;Hiroshi Hirai
• 通讯作者: Hiroshi Hirai

T_x-approaches to multiflows and metrics, In : S.Iwata (ed.)

T_x-多流和指标的方法，见：S.Iwata（编辑）

• 发表时间: 2010
• 期刊: Combinatorial Optimization and Discrete Algorithms, RIMS Kokyuroku Bessatsu 23
• 作者: Nobuhiro Asai;Nobuhiro ASAI;Nobuhiro Asai;Hiroshi Hirai;Nobuhiro ASAI;Hiroshi Hirai
• 通讯作者: Hiroshi Hirai

最大多品種流問題の双対有界分数性

最大品种流问题的对偶有界分数

• 发表时间: 2008
• 作者: Hiroshi Hirai;Hiroshi Hirai;Hiroshi Hirai;Hiroshi Hirai;平井広志
• 通讯作者: 平井広志