权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

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

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

基本信息

批准号：
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) に採択された．

This research project focuses on the optimization of polyhedra, especially on the utilization of complex polyhedra and the utilization of polyhedra. The main results of this research in 2022 are as follows: 1. The problem of multi-dimensional optimization is classical and important. In addition, there are many problems in polynomial time, such as urgent problems, difficult problems, and so on. In this paper, we study the design of the exponential constraint expression for the polynomial time domain. This is the first time that the goal has been achieved. This research was recorded in Mathematical Programming Journal of Mathematical Optimization in 2022. Other important results are presented in this paper. The shortest point element problem is related to polynomial time design. The shortest path problem is the solution of a polyhedron, the combinatorial optimization problem is solved in polynomial time, and the shortest point prime problem is the existence of a polynomial time problem that remains unresolved. In this paper, we study the condition of the shortest point element problem, the initial chaotic polynomial time problem and the problem of the shortest point element. International Symposium on Algorithms and Computation (ISAAC).

项目成果

期刊论文数量（21）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

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

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

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