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

点击翻译按钮获取中文摘要

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