離散的対象の上の効率的なアルゴリズム設計の統一的理論構築

建立离散对象高效算法设计的统一理论

• 批准号: 26887011
• 负责人: 喜多 奈々緒
• 金额: $ 1.58万
• 依托单位: The University of Tokyo
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Research Activity Start-up
• 财政年份: 2014
• 资助国家: 日本
• 起止时间: 2014-08-29 至 2016-03-31
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-26887011/
• 关键词: グラフ; アルゴリズム

本年度は研究計画のうち基礎となる部分に取り組んだ．まず，既知の結果である「完全マッチングをもつ一般のグラフの標準分解」についてこれを与える既存の証明を見直し整理・簡略化を行った．また，完全マッチングを持つとは限らない場合も含めた一般のグラフに対する標準分解へと拡張し，これらを論文にまとめた．次に，マッチングの一般化の一種として知られている奇ジョインと呼ばれる概念について研究を進めた．より具体的にはKotzig-Lovasz 分解とよばれるマッチング理論の分解型構造定理を一般化し，奇ジョイン版Kotzig-Lovasz 分解を与えることに成功した．奇ジョインはマッチング理論のみならず，最短路問題や多品種流問題など多くの代表的な問題との関連が深いため，この結果自体が今後多くの応用を生み出すことが期待できる．また一方で，一つ目の成果をさらに掘り下げ，マッチング理論と離散最適化分野で重要な概念である劣モジュラ関数との関係を探ることにも取り組んだ．最大マッチング問題の双対問題の最適解は与えられたグラフ上に定義される劣モジュラ関数や，あるいはその一般化の最小化問題の解集合として把握できることが知られている．しかし，これには実質的な対象となるグラフクラスがごく一部に限られているなどの問題がある．これに対し本研究では，この既存の結果における欠点を克服した結果を得るべく，マッチングのグラフ理論的構造を精査することで新たな束論的性質を明らかにした．これによりマッチング理論と劣モジュラ関数の関係を基にした離散最適化の理論展開に新たな発展が期待できる．

今年，我们做了研究计划的基础部分。首先，我们回顾并简化了已知结果“具有完美匹配的一般图的标准分解”的现有证明。我们还扩展了一般图的标准分解，包括不一定具有完美匹配的情况，并在论文中进行了总结。接下来，我们对称为奇数连接的概念进行了研究，它被称为匹配的泛化类型。更具体地说，我们推广了匹配理论的分解结构定理，称为 Kotzig-Lovasz 分解，并成功给出了 Kotzig-Lovasz 分解的奇连接版本。奇连接不仅与匹配理论密切相关，而且与最短路径问题和多物种流问题等许多代表性问题密切相关，因此该结果本身有望在未来产生许多应用。另一方面，我们还深入研究了第一个结果，探讨了匹配理论与子模函数之间的关系，这是离散优化领域的一个重要概念。众所周知，最大匹配问题的对偶问题的最优解可以理解为给定图上定义的子模函数，或者理解为其泛化的最小化问题的解集。然而，这样做也存在一些问题，例如目标图类仅限于少数几个。相比之下，在本研究中，我们通过检查匹配的图论结构来阐明新的束理论属性，以获得克服现有结果中的这些缺点的结果。因此，我们可以期待基于匹配理论和子模函数之间关系的离散优化理论的新发展。

项目成果

劣モジュラ性・束代数・半順序集合について

关于子模性、丛代数和部分有序集

• 发表时间: 2014
• 作者: 山岸正和;三津井親彦;佐藤寛泰;山野昭人;竹谷純一;岡本敏宏;喜多 奈々緒
• 通讯作者: 喜多 奈々緒