組合せ最適化における多面体手法の高度化

组合优化中多面体方法的复杂性

• 批准号: 20K11692
• 负责人: 小林 佑輔
• 金额: $ 2.83万
• 依托单位: Kyoto University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2020
• 资助国家: 日本
• 起止时间: 2020-04-01 至 2024-03-31
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-20K11692/
• 关键词: 組合せ最適化; アルゴリズム; 多項式時間

本研究計画は組合せ最適化における多面体的アルゴリズムの高度化を目的とするものであり，特に，「拡張定式化の利用」，「複数の多面体の利用」の2点に注目している．2022年度の主要な成果として，ある種の制約付き重み付き2マッチング問題に対する初の多項式時間アルゴリズムの設計が挙げられる．重み付き2マッチング問題は，多面体的アプローチを用いてアルゴリズムを設計することのできる組合せ最適化における古典的かつ重要な問題である．しかし，付加的な制約を課すと問題は急激に難しくなり，多項式時間アルゴリズムが知られていない問題が数多く存在している．本研究では，ある種の制約付き重み付き2マッチング問題に対して，指数本の制約式を持つ拡張定式化を用いて実行可能解全体を表現するという，今までにないアプローチを用いて多項式時間アルゴリズムを設計している．これはまさに当初目指していた通りの「拡張定式化を利用して多面体的アルゴリズムを高度化する成果」であると言える．この研究は前年度以前から継続して取り組んでいたものであり，2022年度に数理最適化の主要誌である Mathematical Programming誌に採録された．その他の重要な成果として，最短点素パス問題に対する多項式時間アルゴリズムの設計が挙げられる．最短路問題は多面体的に解釈でき，多項式時間で解ける組合せ最適化問題であるが，その拡張である最短点素パス問題は多項式時間アルゴリズムの存在が未解決である．本研究では，ある種の条件をみたす最短点素パス問題に対して，初の乱択多項式時間アルゴリズムを与えている．この成果は，アルゴリズム理論の主要国際会議である International Symposium on Algorithms and Computation (ISAAC) に採択された．

该研究项目旨在推进组合优化中的多面体算法，并特别关注两点：“扩展公式的使用”和“多重多面体的使用”。 2022 年的一项重大成就是针对某些约束加权 2 匹配问题设计了第一个多项式时间算法。加权2匹配问题是组合优化中的一个经典且重要的问题，可以使用多面体方法来设计算法。然而，当施加额外的约束时，问题很快就会变得困难，并且有许多问题的多项式时间算法是未知的。在这项研究中，我们使用一种前所未有的方法，使用带有指数约束公式的扩展公式来表达多项式时间内某种类型的约束加权2匹配问题的整个可行解。可以说，这正是我们最初的目标：“利用扩展公式促进多面体算法的进步”。这项研究从去年开始就一直在进行，并于 2022 年被数学优化主要期刊 Mathematical Planning 接收。其他重要成果包括最短点不相交路径问题的多项式时间算法的设计。最短路径问题是一个组合优化问题，可以用多面体术语解释，并且可以在多项式时间内求解，但作为其扩展的最短点不相交路径问题的多项式时间算法的存在仍未得到解决。在本研究中，我们为满足某些条件的最短点不相交路径问题提供了第一个随机多项式时间算法。该成果被国际算法理论重大会议ISAAC（International Symposium on Algorithms and Computation，ISAAC）接受。

项目成果

Monotone edge flips to an orientation of maximum edge-connectivity a la Nash-Williams

单调边缘翻转到最大边缘连通性的方向，如纳什-威廉姆斯

• DOI: 10.1145/3561302
• 发表时间: 2023
• 期刊: ACM Transactions on Algorithms
• 影响因子: 1.3
• 作者: Takehiro Ito;Yuni Iwamasa;Naonori Kakimura;Naoyuki Kamiyama;Yusuke Kobayashi;Shun-ichi Maezawa;Yuta Nozaki;Yoshio Okamoto;Kenta Ozeki
• 通讯作者: Kenta Ozeki

TU Dortmund 大学(ドイツ)

多特蒙德工业大学（德国）

Lyon 大学/Bordeaux 大学(フランス)

里昂大学/波尔多大学（法国）

Market Pricing for Matroid Rank Valuations

Matroid 排名估值的市场定价

• DOI: 10.1137/20m1386335
• 发表时间: 2021
• 期刊: SIAM Journal on Discrete Mathematics
• 影响因子: 0.8
• 作者: Kristof Berczi;Naonori Kakimura;Yusuke Kobayashi
• 通讯作者: Yusuke Kobayashi

An Improved Deterministic Parameterized Algorithm for Cactus Vertex Deletion

• DOI: 10.1007/s00224-022-10076-x
• 发表时间: 2020-12
• 期刊: Theory of Computing Systems
• 影响因子: 0.5
• 作者: Yuuki Aoike;Tatsuya Gima;T. Hanaka;Masashi Kiyomi;Yasuaki Kobayashi;Yusuke Kobayashi;Kazuhiro Kurita;Y. Otachi