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

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

• 批准号: 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パス頂点被覆問題やソーティングボールパズル，遷移問題全般の困難性の証明の重要なツールである制約論理等，組合せ遷移に関する幅広い研究成果を得ることが出来た．

This year, compared with the previous year, the research project has two objectives, one of which is the central task of "the current time for good solution and development". 2."Convenience and high efficiency" is the key to the success of the project. The difficulty of the vertex color problem and the optimization of the migration problem are related to the ease of the surface and the result. Specifically, each category includes the number of colors less than 2, and the entry force is difficult to calculate when the number of colors is less than 2. In one case, the color number is changed to 1, and the color number is changed to 1. The results of the conference were presented orally at the WALCOM 2023 International Conference on Computing. In 2005, the International Journal of Computer Mathematics: Computer Systems Theory published a paper on color migration and optimization migration, which was published in the International Journal of Computer Mathematics. In this paper, we present a paper entitled "Journal of Combinatorial Optimization" on the optimal transfer problem of independent set problems. He also pointed out that it is difficult to prove the general difficulty of migration problem, such as the restriction logic, and the combination of migration problems.

项目成果

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

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

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

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

On solving independent set reconfiguration problems with bounded model checking

用有界模型检验解决独立集重构问题

• 发表时间: 2022
• 作者: Takahisa Toda;Takehiro Ito;Jun Kawahara;Takehide Soh;Akira Suzuki and Junichi Teruyama
• 通讯作者: Akira Suzuki and Junichi Teruyama

Akira Suzuki's Web Site

铃木晃的网站