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

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

• 批准号: 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