代教的および確率的手法による離散構造の限界の究明

本研究では、代数的手法および確率的手法を用いて、置換族の構成、電子商取引、 VLSI計算、可逆計算、および耐故障計算などに関する離散構造の限界を解明した、置換族の構成に関しては、電子文書間の高速な類似性ツールとして応用が知られているκ限定ε近似的最小値独立置換族Fに対して、一般分布上で定義される置換族Fを行列Uにより定式化し、その行列Uの階数を評価することにより置換族Fのサイズの良好な下界を導出した。電子商取引に関しては、最適選好マッチング問題において、顧客集合が複数の重み付きグループに分割されているとき、顧客数n商品数mの比に関して、乱択化最適選好マッチングが存在するためのほほ合致する上界と下界を導出した(これは、既に知られている顧客集合が1つグループである場合の乱択化最適選好マッチングが存在するための顧客数nと商品数mの比に関する上界・下界の拡張である)。まだ、商品価格設定問題に関しては、正価格モデルおよび無損失割引モデルにおいて見積価格が制限された場合に対して、確率的手法を用いることで,グラフ価格設定問題・線状高速道路問題・環状高速道路問題の良好な近似アルゴリズムを提案した。VLSI計算に関しては、3次元チャネル配線問題がNP困難であることを明らかにした。可逆計算に関しては、可逆回路の縮退故障に対する最小完全テスト集合生成問題がNP困難であることを示した。耐故障計算に関しては、様々なネ ットワークに対して効率的な確率的耐故障ネットワークを構成する統一的な手法を提案した。

本研究では、代数的手法および確率的手法を用いて、置換族の構成、電子商取引、 VLSI計算、可逆計算、および耐故障計算などに関する離散構造の限界を解明した、置換族の構成に関しては、電子文書間の高速な類似性ツールとして応用が知られているκ限定ε近似的最小値独立置換族Fに対して、一般分布上で定義される置換族Fを行列Uにより定式化し、その行列Uの階数を評価することにより置換族Fのサイズの良好な下界を導出した。電子商取引に関しては、最適選好マッチング問題において、顧客集合が複数の重み付きグループに分割されているとき、顧客数n商品数mの比に関して、乱択化最適選好マッチングが存在するためのほほ合致する上界と下界を導出した(これは、既に知られている顧客集合が1つグループである場合の乱択化最適選好マッチングが存在するための顧客数nと商品数mの比に関する上界・下界の拡張である)。まだ、商品価格設定問題に関しては、正価格モデルおよび無損失割引モデルにおいて見積価格が制限された場合に対して、確率的手法を用いることで,グラフ価格設定問題・線状高速道路問題・環状高速道路問題の良好な近似アルゴリズムを提案した。VLSI計算に関しては、3次元チャネル配線問題がNP困難であることを明らかにした。可逆計算に関しては、可逆回路の縮退故障に対する最小完全テスト集合生成問題がNP困難であることを示した。耐故障計算に関しては、様々なネ ットワークに対して効率的な確率的耐故障ネットワークを構成する統一的な手法を提案した。