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

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

基本信息

批准号：
21K17707
负责人：
土中哲秀
金额：
$ 2.91万
依托单位：
Kyushu University (2022)Nagoya University (2021)
依托单位国家：
日本
项目类别：
Grant-in-Aid for Early-Career Scientists
财政年份：
2021
资助国家：
日本
起止时间：
2021-04-01 至 2025-03-31
项目状态：
未结题

项目摘要

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

在本研究中，我们将使用近似技术和参数化技术来设计计算困难问题的算法，并通过结合这些技术，为克服现有算法局限性的高速、高精度算法设计方案奠定基础。今年，我们主要致力于针对计算困难的图优化问题设计近似算法和参数化算法。下面，我们将摘录结果并解释细节。 (1) 一般的优化问题是找到一个解的问题，但在现实世界中，可能会出现出现多个最优解并从中选择合适的解的情况。在这种情况下，最好提出有些不同的解决方案，而不是提出多个相似的解决方案。针对这种情况，提出了考虑多个解决方案的多样性的多样性最大化问题。在本研究中，我们为此类问题构建了一个近似算法设计框架。该框架包含的问题包括最大分集匹配问题、最大分集公共拟阵问题和最大分集最小割问题。该研究成果被人工智能领域顶级会议AAAI2023接受。 (2) 寻找图中的密集子图是图探索的有效方法之一。在本研究中，我们针对寻找最稠密 k 顶点子图的最稠 k 子图问题，设计了一种适用于各种图参数的固定参数简单算法。特别是，我们设计了一种在 O*(2^p) 时间内运行的算法，其中当从图中删除 p 个顶点时，团宽度变得恒定。这项研究阐明了有关主图参数的最稠 k 子图问题参数化的计算复杂性。这项研究的结果被《组合优化杂志》接受。

项目成果

期刊论文数量（11）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

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

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

DOI：
发表时间：
2022
期刊：
影响因子：
0
作者：
杉山康恭;土中哲秀;小野廣隆
通讯作者：
小野廣隆

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

DOI：
10.1609/aaai.v37i4.25511
发表时间：
2022-01
期刊：
ArXiv
影响因子：
0
作者：
T. Hanaka;Masashi Kiyomi;Yasuaki Kobayashi;Yusuke Kobayashi;Kazuhiro Kurita;Y. Otachi
通讯作者：
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

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