最適化計算型クエリーのためのプリプロセッシングアルゴリズム論

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

予め計算しておいた付加的な補助情報を元に高速に所望の解を計算する計算スキームを「最適化計算型クエリー」とそれを実現する「プリプロセッシング」と呼び，この最適化計算型クエリー＋プリプロセッシングのための新たなアルゴリズム論を展開する．最適化計算型クエリーのプリプロセッシングには，付加する補助情報の量と最適化自体の計算量の関係，プリプロセッシングに要する計算量と最適化自体の計算量の関係等，各種のトレードオフ関係が存在する．この新しい融合モデルにおけるプリプロセッシングのための汎用的なアプローチを構築し，実装・評価を通して新たなアルゴリズム設計論を展開するのが本研究提案の大方針である．2022年度は2021年度に実施したグラフ最適化問題への応用のための局所的な最適構造情報保存のための計算量研究を発展させるとともに，本格的に最適化計算型クエリーのためのプリプロセッシングの問題のターゲットを定め研究に取り組んだ．ターゲットとして選んだ問題は2021年12月に国際会議ISAAC2021の最優秀論文「外平面グラフにおけるビアパス問題」で提案されたビアパス問題である．ビアパス問題は寄り道型の最短路問題であり，数少ないプリプロセッシング研究における成功例である最短路問題の一般化でもある．同論文では外平面グラフの構造を利用した最適化計算型クエリーに点数の逆アッカーマン関数のオーダー（つまり実質的には定数時間）で答えるためのプリプロセッシング法を提案している．我々はその結果を外平面グラフの上位クラスである直並列グラフに対して拡張可能であるかなどについて考察を行い，包括的な最適化クエリ＋プリプロセッシング計算のスキームを得た．2023年5月現在，論文を執筆・投稿準備中である．