組合せ遷移による常時稼働型システムの構成最適化

使用组合转换优化始终在线系统的配置

• 批准号: 20K11666
• 负责人: 鈴木 顕
• 金额: $ 2.83万
• 依托单位: Tohoku University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2020
• 资助国家: 日本
• 起止时间: 2020-04-01 至 2024-03-31
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-20K11666/
• 关键词: 組合せ遷移; 最適化遷移; グラフアルゴリズム; アルゴリズム; グラフ理論

本年度は昨年度に引き続き本研究計画の2つの目標の内，1つ目の目標である「現実的な時間でより良い解を求めるアルゴリズムの開発」を中心に従事した．また，2つ目の「利便性の高いプログラムの実装と公開」にも従事した．中でも大きな成果は，リスト頂点彩色問題の最適化遷移問題に関して，困難性容易性の両面から結果を得ることができた．具体的には，各リストに含まれる色数が2以下の場合や，入力グラフをバンド幅やパス幅が定数の二部グラフに制限したとした場合ですら計算困難であることを示した．一方で，パス幅が1の場合に，色数をパラメータとしたFPTアルゴリズムや，色数と入力グラフの頂点被覆数をパラメータとしたFPTアルゴリズムを与えた．これらの結果は既に「アルゴリズムと計算に関する査読付き国際会議（WALCOM 2023）」で口頭発表を行った．また，昨年より継続している彩色遷移問題の最適化遷移問題に関しては，「情報数学と計算機科学に関する査読付き学術誌（International Journal of Computer Mathematics: Computer Systems Theory）」に採択され，既に発行済みである．さらに，本研究課題採択前から取り組んでいた独立集合問題の最適化遷移問題に関する論文が「組合せ最適化に関する査読付き学術誌（Journal of Combinatorial Optimization）」で発行された．他にも，kパス頂点被覆問題やソーティングボールパズル，遷移問題全般の困難性の証明の重要なツールである制約論理等，組合せ遷移に関する幅広い研究成果を得ることが出来た．

从去年开始，今年，我专注于该研究计划的两个目标中的第一个“开发算法在现实时期找到更好的解决方案”。他还从事第二个“实施和发布高方便的计划”。最重要的结果是，从两个难度级别获得了列表顶点着色问题的优化过渡问题。具体而言，即使每个列表中包含的颜色数为2或更小时，或者输入图仅限于具有恒定带宽和路径宽度的两部分图时，计算也很困难。另一方面，当路径宽度为1时，我们提供了一种颜色数量作为参数的fpt算法，以及带有颜色数量和输入图的顶点覆盖率的FPT算法作为参数。这些结果已经在“经过同行评审的算法和计算国际会议（Walcom 2023）”上进行了口头介绍。此外，自去年被选为“国际计算机数学杂志：信息数学和计算机科学的计算机系统理论”以来，针对着色过渡问题的优化过渡问题已经发表。此外，在采用该研究主题之前已经解决的独立集问题的优化过渡问题的论文发表在“同行评审的组合优化杂志”中（Combinatorial优化杂志）。我们还取得了有关组合过渡的广泛研究结果，例如K-PASS顶点覆盖问题，分类球形难题和约束逻辑，这些逻辑是证明过渡问题难度的重要工具。

项目成果

Parameterized complexity of optimizing list vertex-coloring through reconfiguration

通过重新配置优化列表顶点着色的参数化复杂度

• DOI: 10.1007/978-3-031-27051-2_24
• 发表时间: 2023
• 期刊: Proceedings of the 17th International Conference and Workshops on Algorithms and Computation (WALCOM 2023), Lecture Notes in Computer Science (LNCS)
• 作者: Yusuke Yanagisawa;Akira Suzuki;Yuma Tamura and Xiao Zhou
• 通讯作者: Yuma Tamura and Xiao Zhou

Incremental Optimization of Independent Sets Under the Reconfiguration Framework

• DOI: 10.1007/978-3-030-26176-4_26
• 发表时间: 2019-01-01
• 期刊: COMPUTING AND COMBINATORICS, COCOON 2019
• 作者: Ito, Takehiro;Mizuta, Haruka;Suzuki, Akira
• 通讯作者: Suzuki, Akira

Max-Min 3-Dispersion Problems

最大-最小 3-色散问题

• 发表时间: 2019
• 期刊: Lecture Notes in Computer Science
• 作者: T. Horiyama;S. Nakano;T. Saitoh;K. Suetsugu;A. Suzuki;R. Uehara;T. Uno;K. Wasa
• 通讯作者: K. Wasa

ウォータールー大学/アルバータ大学(カナダ)

滑铁卢大学/阿尔伯塔大学（加拿大）

Parameterized complexity of independent set reconfiguration problems

独立集重构问题的参数化复杂度

• DOI: 10.1016/j.dam.2020.01.022
• 发表时间: 2020
• 期刊: Discrete Applied Mathematics
• 影响因子: 1.1
• 作者: Ito Takehiro;Kaminski Marcin;Ono Hirotaka;Suzuki Akira;Uehara Ryuhei;Yamanaka Katsuhisa
• 通讯作者: Yamanaka Katsuhisa