離散境界構造に基づく高速アルゴリズム

基于离散边界结构的快速算法

• 批准号: 22KJ0566
• 负责人: 隈部 壮
• 金额: $ 1.41万
• 依托单位: The University of Tokyo
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for JSPS Fellows
• 财政年份: 2023
• 资助国家: 日本
• 起止时间: 2023-03-08 至 2024-03-31
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-22KJ0566/
• 关键词: 分割統治法; リプシッツ連続性; 平均低感度アルゴリズム; 動的計画法

当研究は、離散境界構造に関する研究を行っており、その一環としてリプシッツ連続なアルゴリズムという概念を提案した。リプシッツ連続性とは、アルゴリズムのロバストネスを示す指標であり、小さな変化が入力されたときにアルゴリズムの出力がどの程度変化するかを示すものである。リプシッツ連続なアルゴリズムを構築するためには、しばしば分割統治法を用いるのが有用である。ここに分割統治法とは、大きな問題を小さな問題に分割し、それぞれを解決することで全体の問題を解決する方法である。この手法を用いることで、離散境界構造に着目し、特に最短路問題と呼ばれるグラフ上の問題に対し、リプシッツ連続なアルゴリズムを開発することができる。リプシッツ連続性は、アルゴリズムのロバストネスを示す指標であり、再現性や敵対的攻撃への頑強性を保証するものである。具体的には、リプシッツ連続なアルゴリズムは、入力データのわずかな変化にも敏感に反応することがなく、安定した出力を保証することができる。その性質が、再現性の担保や敵対的攻撃への頑強性へとつながっており、その根本には離散境界構造の存在があると考えられる。

When studying discrete boundary structure, we propose a new concept of "one ring" and "two rings". The change in the degree of input force and output force of the engine is indicated by the indicator of the engine's continuity and output. The method of dividing governance is useful in the construction of a new system. The method of dividing the problem into two parts, namely dividing the problem into two parts and solving the problem as a whole, This method is used to solve the problem of discrete boundary structure, especially the shortest path problem. The connectivity of the interface is guaranteed by the performance indicators of the interface, reproducibility and tenacity of enemy attacks. The concrete structure of the structure is: the structure of the structure, and the structure of the structure. Nature, reproducibility, security, enemy attack, tenacity, fundamentals, existence of discrete boundary structures

项目成果

Interval Query Problem on Cube-Free Median Graphs

无立方中值图上的区间查询问题

• 发表时间: 2021
• 期刊: 32nd International Symposium on Algorithms and Computation (ISAAC 2021)
• 作者: Mitsuaki Obara;Takayuki Okuno;and Akiko Takeda;Soh Kumabe
• 通讯作者: Soh Kumabe