（邦訳：オンラインナップサックと関連する諸問題に対するアルゴリズム論的研究）
| 河瀬 康志 東京工業大学社会理工学研究科社会工学専攻松井知己研究室 助教 |
［背景］未来の情報がわからない中での最適化
［問題］はじめからすべての入力を知っていた場合に対し，どの程度よい解を得られるかという競合比の解析
［貢献］オンラインナップサック問題などに対して良い競合比をもつアルゴリズムの提案
［問題］はじめからすべての入力を知っていた場合に対し，どの程度よい解を得られるかという競合比の解析
［貢献］オンラインナップサック問題などに対して良い競合比をもつアルゴリズムの提案
最適化問題や探索問題などの古典的な計算機科学の問題では，はじめにすべての情報を知った後で，解を求めるという研究がなされてきた．しかし，インターネットのルーティングや仕事の割当て問題，株の取引などの実用上の問題では，未来の情報が分からない中で逐次的に選択をする必要があることも多い．このような状況で，なるべく後から後悔をしない選択を求める問題をオンライン問題といい，それに対するアルゴリズムをオンラインアルゴリズムという．オンラインアルゴリズムでは未来の情報を知ることなく選択を行う必要があるため，最適な解を出力できるとは限らない．そこで，オンラインアルゴリズムの性能は，はじめにすべての入力を知っていた場合に対し，どの程度よい解を出力できるかという競合比で評価されることが多い．本研究では，主にオンライン版のナップサック問題の研究を行った．ナップサック問題は組合せ最適化分野で最も研究がなされている問題の1つであり，実世界への多くの応用をもつ．古典的なナップサック問題では，容量をもつナップサックが1つと，価値とサイズをもつ品物の集合が与えられる．このとき，ナップサックに入れられる（すなわちサイズの総和が容量を超えない） という制約の下で，価値の総和を最大にする品物集合を求める問題である．オンラインナップサック問題では，初めに，ナップサックの容量が与えられ，次に，品物集合が逐次的に与えられる．そして，各品物がくるごとに，ナップサックに入れるか入れないかを決める．
本研究では，特にキャンセル可能な場合を扱った．キャンセル可能の設定では，品物をナップサックに入れるとき，ナップサック内の品物をいくつか捨てることもできる．キャンセルにはコストがかかる場合とそうでない場合があり，コストがかかる場合は「買戻し問題」という名前で研究がなされている．この問題は，検索エンジンによる広告販売をモデル化したものであり，キャンセルコストは，機会損失保証や事務手数料，配送料などとして現れる．
本研究では，以下の成果を得た．
- 無料キャンセル可能オンラインナップサック問題で，品物の価値が重さに比例する場合について，乱数を用いることで既存のアルゴリズムよりもよい競合比をもつアルゴリズムを提案した．
- 無料キャンセル可能オンラインナップサック問題で，品物の価値と重さの間に凸関数で表される関係がある場合について，よい競合比をもつアルゴリズムを提案した．
- 品物をキャンセルするためには，その品物の価値に比例したコストがかかるオンラインナップサック問題について，競合比の意味で最適なアルゴリズムを構成した．
- 品物をキャンセルするためには，品物によらず定められたコストがかかるオンラインナップサック問題について，競合比の意味で最適なアルゴリズムを構成した．
また，その他にも，時間依存スケジューリング問題や自由順序秘書問題の自然な拡張である「最適合性順問題」を導入し，その計算複雑度を議論した．
（2014年4月30日受付）