Algorithm Design for k-Constrained Combinatorial Optimization Problems

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

組合せ最適化問題に対する解法アルゴリズムは，与えられた制約条件を満たす実行可能解の中から，目的関数の値を最大または最小にするような解を見つけることが目的となる．従来，最適化問題に対するアルゴリズム設計の際には，制約条件を満たす解をゼロから求めることを仮定しているが，実際の場面では，ある程度の解が既に求められており，その解から始めて，より良い更新解を求めることも多い．本研究では，制約条件に加えて，初期解および初期解からの変更制約が与えられた元での組合せ最適化問題を対象に計算容易性・困難性の解明を目標としている．今年度の主要な研究結果は以下である．(1) 辺重み付き二部グラフと初期のマッチング辺集合が与えられたときに，変更できるマッチング辺の上界が与えられたときに，出来るだけ辺重みの合計が最大となる問題について検討を行った．従来の近似アルゴリズムを改善するアルゴリズムを設計できることを第75回電気・情報関係学会九州支部連合大会(2022年度)において公表した．(2) 2つの文字列が与えられたとき，2つの文字列に共通な部分文字列の中で，最長となる部分文字列は多項式時間で見つけることが出来る．これを初期共通部分文字列として，さらに入力文字列に追加可能な文字集合が与えられたときに，共通部分文字列を出来るだけ長くするように文字追加する埋め込み型の最長共通部分文字列問題について検討を行った．類似問題と多項式時間の差の範囲で等価であることを用いることで指数時間厳密アルゴリズムを提案した．研究成果については33rd Annual Symposium on Combinatorial Pattern Matching (CPM 2022)において公表を行った．