離散最適化に対する固定パラメータアルゴリズムの深化：多項式時間FPTと実用化

深化离散优化的固定参数算法：多项式时间FPT及实际应用

• 批准号: 17K00017
• 负责人: 宇野 裕之
• 金额: $ 3万
• 依托单位: Osaka Metropolitan University (2022)Osaka Prefecture University (2017-2021)
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2017
• 资助国家: 日本
• 起止时间: 2017-04-01 至 2024-03-31
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-17K00017/
• 关键词: 固定パラメータアルゴリズム; 固定パラメータ容易性; ネットワーク解析; 近傍多様性; ネットワーク中心性; クラスター編集; 実ネットワーク; 頂点被覆; パラメータ化計算; ハミルトン性; 媒介中心性; コミュニティ発見; 資金循環問題; 離散最適化; パラメータ化計算複雑さ; 多項式時間アルゴリズム

本研究は，理論計算機科学における計算複雑さおよびアルゴリズム理論の分野で急速な進展を遂げているパラメータ化計算という枠組みのもとで，離散最適化に対する率的なアルゴリズムの設計技法として確立しつつある固定パラメータアルゴリズム理論を扱っている．その理論がもつ，何らかの特徴をもつ実データに対してアルゴリズムを高速に動作させるという理念に鑑み，理論的な成果を挙げると同時に固定パラメータアルゴリズム研究を実用化の段階へ推し進めることを目的とする．本研究は，当初設定した研究期間を経過したが，コロナ感染症による進捗の遅れから研究機関を再延長した．６年度目である令和４年度は，前年度までの方針を踏襲し，理論的な研究を継続するとともに実用的な方向への挑戦を推し進めた．具体的には，まずはじめに理論面からは，Double-Threshold Graph と命名したグラフの認識問題に対して多項式時間アルゴリズムを設計し公表していたが，これを雑誌論文とした．またあらたにグラフ描画に関する重要問題を考察し，それに対する固定パラメータアルゴリズムの開発に着手した．実用的な方向では，ネットワーク解析分野で頻出するネットワーク中心性を厳密に計算する問題を継続して扱い，なかでも最も重要である頂点媒介中心性に対するアルゴリズムの実装の高速化を試みている．また，固定パラメータアルゴリズム分野で基本的な問題の一つであるグラフ燃焼問題に対する固定パラメータアルゴリズムに関する実証実験も継続し，実ネットワークを入力としたときに有効となるカーネル化や有界探索木などの手法を検証している．

在参数计算的框架下，这项研究是作为一种随机算法设计技术，用于离散优化，在理论计算器科学和算法理论领域中，它一直在迅速发展。考虑到该理论是在具有某些特征的实际数据的高速操作算法的理念中，其目的是促进理论结果并促进固定参数算法研究以实际使用。这项研究已在最初设定的研究期后重新扩展，但由于电晕感染而导致的进展已延迟。在第4财政年度，即第六年，即41财年的第四年，遵循了上一年的政策，继续进行了理论研究，并朝着实际方向提高了挑战。具体而言，从理论方面来看，在名为Double-Threshold图的图形识别问题上设计和发表了多个时间算法，但这是杂志论文。我们还考虑了与图形图有关的重要问题，并开始针对它开发固定参数算法。在实际的方向上，严格计算网络分析领域经常出现的网络中心的问题正在试图加快垂直瘀伤中心算法的实现，这是最重要的。此外，关于图形燃烧问题的固定参数算法的演示实验，该实验是固定参数算法中的基本问题之一，并且在输入实际网络时继续有效，例如内核或世界搜索树。

项目成果

How efficiently can nets of polycubes pack a rectangle?

多立方体网能多有效地包装一个矩形？

• 发表时间: 2018
• 作者: E. D. Demaine;M. L. Demaine;R. Uehara;Y. Uno and A. Winslow
• 通讯作者: Y. Uno and A. Winslow

媒介中心性のグラフ分解を用いた効率的な計算および その実ネットワークへの適用

利用介数中心性的图分解进行高效计算及其在真实网络中的应用

• 发表时间: 2017
• 作者: 伊野波竜矢;定兼邦彦;宇野裕之;米林悠真
• 通讯作者: 米林悠真

Settlement fund circulation problem

结算资金流转问题

• DOI: 10.1016/j.dam.2019.03.017
• 发表时间: 2019
• 期刊: Discrete Applied Mathematics
• 影响因子: 1.1
• 作者: Hitoshi Hayakawa;Toshimasa Ishii;Hirotaka Ono and Yushi Uno
• 通讯作者: Hirotaka Ono and Yushi Uno

Hyperfiniteness of Real-World Networks

现实世界网络的超有限性

• DOI: 10.1007/s12626-019-00051-3
• 发表时间: 2019
• 期刊: Reviews of Socionetwork Strategies
• 作者: Yutaro Honda;Yoshitaka Inoue;Hiro Ito;Munehiko Sasajima;Junichi Teruyama;Yushi Uno
• 通讯作者: Yushi Uno

Reconfiguring Undirected Paths

重新配置无向路径

• 发表时间: 2019
• 作者: Erik D. Demaine;David Eppstein;Adam Hesterberg;Kshitij Jain;Anna Lubiw;Ryuhei Uehara;Yushi Uno
• 通讯作者: Yushi Uno