Research on algorithms and data structures for solving theoretically hard problems in practical time

本年度は、査読付きジャーナル論文14編（うち国際共著論文3編）と審査のある国際会議発表20編（うち国際共同研究5編）という研究成果をあげることができた。研究成果としては、グラフ上の問題や計算幾何における問題に対して、効率の良い解法を与えるアルゴリズムの開発や、逆に理論的な困難性を示す理論的な結果が主である。新型コロナ禍において、全体で集まっての対面での研究活動はほとんどできず、もっぱら研究分担者たちが個別に連絡を取り合って研究を進展させた中では十分な研究成果であると言えよう。特に2021年11月には、オンラインと対面を組み合わせたハイブリッドな研究合宿を開催し、ある種の並べ替え問題に関する多角的な視点からの研究成果を得た。この問題はコンピュータ・サイエンスの基礎であるソーティング（並べ替え）と密接な関係を持つ問題であり、最近の理論計算機科学の一分野である組合せ遷移に関する問題としても位置づけることができる。また、船舶のコンテナ積み上げ等、様々な応用も考えられる。この研究テーマに対して、最終的には理論的な困難性と、多項式時間で解ける場合と、その具体的な解法アルゴリズムを与えることに成功した。さらに、現実的な時間で解くソルバも開発し、理論的に困難な場合でも、ある程度の規模まで現実的な時間で解が得られることを具体的に示した。このような理論上も応用上も重要な関連を持つ問題に対して得られた一連の研究結果は、問題の困難性と容易性の理論的な解析、さらには理論的な解析から得られる知見を活用した現実的なソルバの開発も含んでおり、本研究プロジェクトにおける重要な研究成果となった。

本年度は、査読付きジャーナル論文14編（うち国際共著論文3編）と審査のある国際会議発表20編（うち国際共同研究5編）という研究成果をあげることができた。研究成果としては、グラフ上の問題や計算幾何における問題に対して、効率の良い解法を与えるアルゴリズムの開発や、逆に理論的な困難性を示す理論的な結果が主である。新型コロナ禍において、全体で集まっての対面での研究活動はほとんどできず、もっぱら研究分担者たちが個別に連絡を取り合って研究を進展させた中では十分な研究成果であると言えよう。特に2021年11月には、オンラインと対面を組み合わせたハイブリッドな研究合宿を開催し、ある種の並べ替え問題に関する多角的な視点からの研究成果を得た。この問題はコンピュータ・サイエンスの基礎であるソーティング（並べ替え）と密接な関係を持つ問題であり、最近の理論計算機科学の一分野である組合せ遷移に関する問題としても位置づけることができる。また、船舶のコンテナ積み上げ等、様々な応用も考えられる。この研究テーマに対して、最終的には理論的な困難性と、多項式時間で解ける場合と、その具体的な解法アルゴリズムを与えることに成功した。さらに、現実的な時間で解くソルバも開発し、理論的に困難な場合でも、ある程度の規模まで現実的な時間で解が得られることを具体的に示した。このような理論上も応用上も重要な関連を持つ問題に対して得られた一連の研究結果は、問題の困難性と容易性の理論的な解析、さらには理論的な解析から得られる知見を活用した現実的なソルバの開発も含んでおり、本研究プロジェクトにおける重要な研究成果となった。