大規模配位空間の最適化理論：離散構造論の視点を中心にして

大规模配置空间的优化理论：聚焦离散结构理论的视角

• 批准号: 20K11670
• 负责人: 岡本 吉央
• 金额: $ 2.83万
• 依托单位: The University of Electro-Communications
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2020
• 资助国家: 日本
• 起止时间: 2020-04-01 至 2024-03-31
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-20K11670/
• 关键词: アルゴリズム理論; 最適化理論; 計算理論; 離散数学; 組合せ遷移

大規模配位空間における最適化問題の研究として，2022年度は以下の研究を行った．(1) ロボットの動作計画は配位空間における典型的な最適化問題である．2次元の単純多角形を環境とし，ロボットが単位円で表される場合において，ロボットの再配置が必ず可能であるための距離制約としてもっとも厳しいものを発見した．研究成果を計算幾何のトップ会議であるSoCG 2022で発表した．(2) 社会選択理論に現れるアイテム交換問題を大規模配位空間における到達可能性問題としてモデル化し，その計算複雑性を解明し，特別な場合の多項式時間アルゴリズムを開発した．研究成果をマルチエージェントシステムの理論に関する国際会議PRIMA 2022で発表した．(3) 完全マッチング多面体上の最短路問題を考察し，一般の場合に計算困難であることを証明し，外平面的グラフに対して多項式時間で解くためのアルゴリズムを設計した．研究成果を離散数学のプレミア論文誌SIAM Journal on Discrete Mathematicsで発表した．

以下研究是在2022年进行的，是关于大规模协调空间优化问题的研究。 （1）机器人运动计划是协调空间中的典型优化问题。我们发现了最严格的距离约束，因为可以将机器人以简单的二维多边形作为环境以及机器人表示为单位圆时将机器人重置为环境。研究结果在SOCG 2022（计算几何学的首席会议）上介绍。 （2）我们对社会选择理论中出现的项目交换问题建模为大规模协调空间中的可及性问题，阐明了其计算复杂性，并为特殊情况开发了多项式时间算法。研究结果在2022年Prima 2022国际多代理系统理论会议上介绍。 （3）我们在完美匹配的多面体上检查了最短路径问题，证明在一般情况下很难计算，并设计了用于在多项式时间内求解外部平面图的算法。研究结果介绍了《 Siam杂志》（SIAM）关于离散数学杂志的离散数学杂志。

项目成果

Graphs with large total angular resolution

具有大总角分辨率的图表

• DOI: 10.1016/j.tcs.2022.12.010
• 发表时间: 2023
• 期刊: Theoretical Computer Science
• 影响因子: 1.1
• 作者: Oswin Aichholzer;Matias Korman;Yoshio Okamoto;Irene Parada;Daniel Perz;Andre van Renssen;Birgit Vogtenhuber
• 通讯作者: Birgit Vogtenhuber

Rectilinear link diameter and radius in a rectilinear polygonal domain

直线多边形域中的直线链接直径和半径

• DOI: 10.1016/j.comgeo.2020.101685
• 发表时间: 2021
• 期刊: Computational Geometry
• 作者: Arseneva Elena;Chiu Man-Kwun;Korman Matias;Markovic Aleksandar;Okamoto Yoshio;Ooms Aur?lien;van Renssen Andr?;Roeloffzen Marcel
• 通讯作者: Roeloffzen Marcel

Submodular Reassignment Problem for Reallocating Agents to Tasks with Synergy Effects

将代理重新分配给具有协同效应的任务的子模块重新分配问题

• DOI: 10.1016/j.disopt.2021.100631
• 发表时间: 2021
• 期刊: Discrete Optimization
• 影响因子: 1.1
• 作者: Naonori Kakimura;Naoyuki Kamiyama;Yusuke Kobayashi;and Yoshio Okamoto
• 通讯作者: and Yoshio Okamoto

Algorithmic Enumeration of Surrounding Polygons

周围多边形的算法枚举

• 发表时间: 2018
• 作者: K. Yamanaka;T. Horiyama;Y. Okamoto;R. Uehara;T. Yamauchi
• 通讯作者: T. Yamauchi

Subgraph Isomorphism on Graph Classes that Exclude a Substructure

排除子结构的图类上的子图同构

• DOI: 10.1007/s00453-020-00737-z
• 发表时间: 2020
• 期刊: Algorithmica
• 影响因子: 1.1
• 作者: Bodlaender Hans L.;Hanaka Tesshu;Kobayashi Yasuaki;Kobayashi Yusuke;Okamoto Yoshio;Otachi Yota;van der Zanden Tom C.
• 通讯作者: van der Zanden Tom C.