Developing Theory of Combinatorial Optimization Based on Matrix Representations

发展基于矩阵表示的组合优化理论

• 批准号: 22K17853
• 负责人: 大城 泰平
• 金额: $ 2.91万
• 依托单位: The University of Tokyo
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Early-Career Scientists
• 财政年份: 2022
• 资助国家: 日本
• 起止时间: 2022-04-01 至 2027-03-31
• 项目状态: 未结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-22K17853/
• 关键词: 組合せ最適化; 代数的アルゴリズム; 線形マトロイドパリティ; 非可換階数; Edmonds問題; 線形代数; マトロイド; 数え上げ

組合せ最適化とは，複数の離散的な選択肢の中から最も良いものを探す問題の枠組みであり，いくつかの組合せ最適化問題は各要素が多変数一次式である「線形記号行列」の階数を計算する問題として表現できる．Lovasz (1989)は，各記号の係数行列が階数2の歪対称行列であるような線形記号行列の階数を計算することで，「線形マトロイドパリティ問題」を解くことができるということを示した．この問題は線形マトロイド交叉やマッチングを含む一般的な問題である．線形記号行列の階数を計算する問題はEdmonds問題とよばれ，乱数を用いずに多項式時間で解くことが可能かどうかが計算量理論における未解決問題の一つとなっている．近年，線形記号行列の各変数を積に関して互いに非可換とみなした場合に定義される「非可換階数」を計算する「非可換Edmonds問題」は決定性多項式時間可解であることが示された．代表研究者は，本年，非可換階数を用いた組合せ最適化問題の表現に取り組んだ．線形マトロイドパリティを表現する行列の非可換階数が，問題の実数緩和版である「分数線形マトロイドパリティ」の最適値に対応するということを示した．すなわち，本行列表現において，記号を可換・非可換とみなすことは，最適化問題の許容解として整数制約をそれぞれ課す・課さないという選択と対応するということを明らかにした．さらにこの事実を基にし，分数線形マトロイドパリティを解く高速アルゴリズムを提案した．本結果は離散アルゴリズム分野のトップ会議SODAで発表した．現在フルバージョンを雑誌に投稿中である．また本年は，3本の論文を機械学習分野のトップ会議NeurIPSで発表した．これらは組合せ最適化問題の行列表現とは直接関係する内容ではないものの，本研究の遂行中に得られた組合せ最適化および線形代数に対する知見を応用したものである．

Lovasz (1989), The coefficient array of each symbol is of order 2 and the order of the array of linear symbols is calculated."Line shape" problem The problem is linear and cross. The problem of calculating the order of a linear symbol array is Edmonds problem. The problem of random numbers is solved in polynomial time. The problem of unsolved problems is solved in computational quantity theory. In recent years, the product of each number of linear symbol arrays is related to the definition of "non-commutative order" and the calculation of "non-commutative Edmonds problem". On behalf of the researcher, this year, the non-commutative order is used in the combination of optimization problems. The non-commutative order of the linear form is equal to the rank of the linear form. The actual numerical mitigation version of the problem shows the optimal value of the "fractional linear form". This is a list of all possible solutions to optimization problems. This is the first time I've ever seen a picture of a guy who's been on the road, and he's been on the road. The results of this study are presented in detail below. Now you can write to me. This year, three papers on mechanical learning were published. This paper presents a method for solving combinatorial optimization problems.

项目成果

Lazy and fast greedy MAP inference for determinantal point process

行列式点过程的惰性和快速贪婪 MAP 推理

• 发表时间: 2022
• 期刊: Proceedings of the 36th Conference on Neural Information Processing Systems (NeurIPS '22)
• 作者: Shinichi Hemmi;Taihei Oki;Shinsaku Sakaue;Kaito Fujii;and Satoru Iwata
• 通讯作者: and Satoru Iwata

Discrete-Convex-Analysis-Based Framework for Warm-Starting Algorithms with Predictions

• DOI: 10.48550/arxiv.2205.09961
• 发表时间: 2022-05
• 期刊: ArXiv
• 作者: Shinsaku Sakaue;Taihei Oki

Sample complexity of learning heuristic functions for greedy-best-first and A* search

贪婪最佳优先和 A* 搜索的学习启发式函数的样本复杂度

• 发表时间: 2022
• 期刊: Proceedings of the 36th Conference on Neural Information Processing Systems (NeurIPS '22)
• 作者: Oki Taihei;Soma Tasuku;Shinsaku Sakaue and Taihei Oki
• 通讯作者: Shinsaku Sakaue and Taihei Oki

Algebraic algorithms for fractional linear matroid parity via non-commutative rank

通过非交换秩实现分数线性拟阵奇偶校验的代数算法

• DOI: 10.1137/1.9781611977554.ch161
• 发表时间: 2023
• 期刊: Proceedings of the 34th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '23)
• 作者: Oki Taihei;Soma Tasuku
• 通讯作者: Soma Tasuku

分数線形マトロイドパリティに対する非可換階数を用いた代数的アルゴリズム

使用非交换秩进行分数线性拟阵奇偶校验的代数算法

• 发表时间: 2023
• 作者: Shinichi Hemmi;Taihei Oki;Shinsaku Sakaue;Kaito Fujii;and Satoru Iwata;Taihei Oki and Tasuku Soma;大城泰平，相馬輔
• 通讯作者: 大城泰平，相馬輔