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

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

• 批准号: 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/
• 关键词: 分割統治法; リプシッツ連続性; 平均低感度アルゴリズム; 動的計画法

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

这项研究正在对离散边界结构进行研究，作为这项研究的一部分，我们提出了Lipschitz连续算法的概念。 Lipschitz的连续性是算法鲁棒性的指标，表明在输入小变化时，算法的输出变化程度。使用分隔和征服方法来构建Lipschitz连续算法通常很有用。在这里，划分和征服方法是一种通过将大问题分为小问题并解决每个问题来解决整个问题的方法。通过使用此技术，可以开发Lipschitz连续算法，尤其是对于称为最短路径问题的图形问题，重点是离散的边界结构。 Lipschitz的连续性是算法鲁棒性的指示，可确保对敌对攻击的可重复性和鲁棒性。具体而言，Lipschitz连续算法对输入数据的轻微变化不敏感，并且可以保证稳定的输出。这种性质导致了敌对攻击的附带重现性和鲁棒性，并且认为从此根源就存在一个离散的边界结构。

项目成果

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