不完全情報下における空間探索及び施設配置に関する理論的研究

当該年度においては，交付申請書で掲げた「動的ネットワークにおける最大後悔最小化を考慮した避難施設配置問題」に関する研究を中心に取り組んだ．最初の成果としては，n個の頂点からなる木状のネットワークにおける最大後悔最小化1施設配置問題に対してO(n^2 log^2 n)時間アルゴリズムを開発したことが挙げられる．前年度の代表研究者らのグループによって，パスネットワーク上の任意の施設における最悪シナリオが，O(n)サイズを持つ特定のシナリオ集合に含まれることを既に示しているが，本成果ではこのパス上での定理を木上に拡張することに成功しており，得られた拡張を基に多項式時間アルゴリズムを構築した．本成果は，昨年度の国際学会において口頭発表されたが，その後同学会より国際論文誌の特別号への招待を受け，本年度採録された．次の成果としては，パスネットワークにおける最大後悔最小化k施設配置問題に対してO(kn^3)時間アルゴリズムを開発したことが挙げられる．まず部分問題として，各頂点の避難者数が固定された場合の避難完了時間最小化施設配置問題に取り組み，パス上のk施設配置問題に対してO(kn log n)時間アルゴリズムを開発し，本年度の国際学会にて発表を行った．本論文は同学会において，最優秀論文賞を受賞し，国際論文誌の特別号への招待を受けた．また，この計算時間はさらに改善され，O(kn)時間アルゴリズムを得た．この部分問題に対するアルゴリズムを用いて，各頂点の避難者数がインターバルで与えられた場合，パス上の最大後悔最小化k避難施設配置問題がO(kn^3)時間で解けることを示し，本年度の国際学会にて発表を行った．また研究代表者らの他にも，動的ネットワーク上の最大後悔最小化施設配置問題を扱う研究が国際会議や国際論文誌に採録されてきており，一定のインパクトを持つ研究を行うことができたと言える．

当該年度においては，交付申請書で掲げた「動的ネットワークにおける最大後悔最小化を考慮した避難施設配置問題」に関する研究を中心に取り組んだ．最初の成果としては，n個の頂点からなる木状のネットワークにおける最大後悔最小化1施設配置問題に対してO(n^2 log^2 n)時間アルゴリズムを開発したことが挙げられる．前年度の代表研究者らのグループによって，パスネットワーク上の任意の施設における最悪シナリオが，O(n)サイズを持つ特定のシナリオ集合に含まれることを既に示しているが，本成果ではこのパス上での定理を木上に拡張することに成功しており，得られた拡張を基に多項式時間アルゴリズムを構築した．本成果は，昨年度の国際学会において口頭発表されたが，その後同学会より国際論文誌の特別号への招待を受け，本年度採録された．次の成果としては，パスネットワークにおける最大後悔最小化k施設配置問題に対してO(kn^3)時間アルゴリズムを開発したことが挙げられる．まず部分問題として，各頂点の避難者数が固定された場合の避難完了時間最小化施設配置問題に取り組み，パス上のk施設配置問題に対してO(kn log n)時間アルゴリズムを開発し，本年度の国際学会にて発表を行った．本論文は同学会において，最優秀論文賞を受賞し，国際論文誌の特別号への招待を受けた．また，この計算時間はさらに改善され，O(kn)時間アルゴリズムを得た．この部分問題に対するアルゴリズムを用いて，各頂点の避難者数がインターバルで与えられた場合，パス上の最大後悔最小化k避難施設配置問題がO(kn^3)時間で解けることを示し，本年度の国際学会にて発表を行った．また研究代表者らの他にも，動的ネットワーク上の最大後悔最小化施設配置問題を扱う研究が国際会議や国際論文誌に採録されてきており，一定のインパクトを持つ研究を行うことができたと言える．