课题基金 / 基金详情

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

大規模配位空間の最適化理論：離散構造論の視点を中心にして
大规模配置空间的优化理论：聚焦离散结构理论的视角
批准号：
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) ロボットの動作計画は配位空間における典型的な最適化問題である．2次元の単純多角形を環境とし，ロボットが単位円で表される場合において，ロボットの再配置が必ず可能であるための距離制約としてもっとも厳しいものを発見した．研究成果を計算幾何のトップ会議であるSoCG 2022で発表した．(2) 社会選択理論に現れるアイテム交換問題を大規模配位空間における到達可能性問題としてモデル化し，その計算複雑性を解明し，特別な場合の多項式時間アルゴリズムを開発した．研究成果をマルチエージェントシステムの理論に関する国際会議PRIMA 2022で発表した．(3) 完全マッチング多面体上の最短路問題を考察し，一般の場合に計算困難であることを証明し，外平面的グラフに対して多項式時間で解くためのアルゴリズムを設計した．研究成果を離散数学のプレミア論文誌SIAM Journal on Discrete Mathematicsで発表した．
期刊论文(35)
专著(0)
科研奖励(0)
会议论文
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
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
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
Algorithmic Enumeration of Surrounding Polygons
周围多边形的算法枚举
DOI： --
发表时间： 2018
期刊：
影响因子： --
作者： [K. Yamanaka, T. Horiyama, Y. Okamoto, R. Uehara, T. Yamauchi]
通讯作者： T. Yamauchi
共 29 条
    Product structures theorems and unified methods of algorithm design for geometrically constructed graphs
    • 批准号：
      23K10982
    • 项目类别：
      Grant-in-Aid for Scientific Research (C)
    • 资助金额：
      $3.0万
    • 财政年份：
      2023
    • 负责人：
      岡本 吉央
    • 依托单位：
      The University of Electro-Communications
    海外基金