グラフ最適化問題に対する高速高精度アルゴリズムの開発

开发快速准确的图优化问题算法

• 批准号: 21K17707
• 负责人: 土中 哲秀
• 金额: $ 2.91万
• 依托单位: Kyushu University (2022)Nagoya University (2021)
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Early-Career Scientists
• 财政年份: 2021
• 资助国家: 日本
• 起止时间: 2021-04-01 至 2025-03-31
• 项目状态: 未结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-21K17707/
• 关键词: グラフアルゴリズム; 計算複雑性; パラメータ化アルゴリズム; 近似アルゴリズム; 固定パラメータ容易性

本研究では，近似技法やパラメータ化技法による計算困難問題へのアルゴリズム設計，およびそれらの技法を組み合わせることにより既存アルゴリズムの限界を打破する高速高精度アルゴリズム設計スキームの基盤構築を行う．本年度は，主に計算困難なグラフ最適化問題に対する近似アルゴリズム，およびパラメータ化アルゴリズムなどの設計に取り組んだ．以下では結果を抜粋して詳細を述べる．(1)通常の最適化問題は解を1つ発見するような問題であるが，現実世界では複数の最適解を提示し，その中から適切な解を選ぶといった状況が考えられる．この際，似たような解を複数提示するのではなくある程度異なる解を提示する方が望ましい．このようなシチュエーションに対して，複数解の多様性を考慮した多様性最大化問題が提案された．本研究では，このようなタイプの問題に対する近似アルゴリズム設計フレームワークを構築した．このフレームワークに含まれる問題として，多様性最大マッチング問題， 多様性最大共通マトロイド問題，多様性最大最小カット問題などが挙げられる．本研究結果は人工知能分野のトップカンファレンスであるAAAI2023に採択された．(2)グラフの中から密な部分グラフを見つけることはグラフ探索の有効なアプローチの一つである．本研究では，k頂点部分グラフで最も密なものを探す最密k-部分グラフ問題に対して，各種グラフパラメータに関する固定パラメータ容易アルゴリズムを設計した．特に，グラフからp頂点削除するとクリーク幅が定数になるようなグラフに対して，O*(2^p)時間で動作するアルゴリズムを設計した．本研究によって，主要なグラフパラメータに関する最密k-部分グラフ問題のパラメータ化計算量が明らかになった．本研究結果は，Journal of Combinatorial Optimizationに採択された．

In this study, approximate techniques are used to solve difficult problems. In this study, similar techniques are used to solve difficult problems. In this study, similar techniques are used to improve the performance of high-speed, high-precision, high-speed, high-precision The main computer calculates the problem of optimization, which is similar to that of the computer, and the design of the system is similar to that of the computer. The following results describe how to solve the problem of optimization. (1) in general, the solution to the optimization problem is similar to the problem of optimization, and the complex number of the world is the most complex. In the middle of the study, you may want to solve the problem. In the world, it is possible to solve the problem that the number of complex numbers indicates the extent of the problem. In this study, the proposal for the maximization of multiplicity is not valid. The problem is similar to that of the design and design of the computer. There is a problem in which there is a problem, a problem with the most common problem, a problem with the most common problem, and a problem with the most common problem. The results of this study show that the artificial knowledge is divided into two parts: one is the artificial knowledge, the other is the AAAI2023. (2) the information in the secret part of the information is very important. There is a lot of information in this study. K part of the security test, the most secret detection, the most secret, the most secret, the most secret. O* (2 ^ p) time-related actions are used to analyze the design of equipment. This study focuses on the most dense k-part of the problem of environmental pollution. The results of this study show that the Journal of Combinatorial Optimization is very accurate.

项目成果

小直径グラフにおける距離制約付きラベリング問題のTSPへの帰着

将小直径图中的距离约束标记问题简化为 TSP

• 发表时间: 2022
• 作者: 杉山 康恭;土中 哲秀;小野 廣隆
• 通讯作者: 小野 廣隆

A Framework to Design Approximation Algorithms for Finding Diverse Solutions in Combinatorial Problems

• DOI: 10.1609/aaai.v37i4.25511
• 发表时间: 2022-01
• 期刊: ArXiv
• 作者: T. Hanaka;Masashi Kiyomi;Yasuaki Kobayashi;Yusuke Kobayashi;Kazuhiro Kurita;Y. Otachi

(In)approximability of maximum minimal FVS

最大最小 FVS 的（In）近似性

• DOI: 10.1016/j.jcss.2021.09.001
• 发表时间: 2022
• 期刊: Journal of Computer and System Sciences
• 影响因子: 1.1
• 作者: Dublois Louis;Hanaka Tesshu;Khosravian Ghadikolaei Mehdi;Lampis Michael;Melissinos Nikolaos
• 通讯作者: Melissinos Nikolaos

Collecting Balls on a Line by Robots with Limited Energy

通过能量有限的机器人收集线上的球

• 发表时间: 2023
• 作者: N. H. Droguett;K. Kurita;T. Hanaka;Y. Otachi;H. Ono
• 通讯作者: H. Ono

Computing Diverse Shortest Paths Efficiently: A Theoretical and Experimental Study

• DOI: 10.1609/aaai.v36i4.20290
• 发表时间: 2021-12
• 作者: T. Hanaka;Yasuaki Kobayashi;Kazuhiro Kurita;See Woo Lee;Y. Otachi