New Development in the Design of Performance Guarantee Algorithms Powered by Mathematical Optimization

ナップサック問題は、単一のナップサックに、サイズの制約を守りつつ価値和が最大となるようにアイテムを詰める問題である。Iwama と Taketomi [ICALP 02]は派生問題として、アイテムが逐次与えられ、かつナップサックに一度詰めたアイテムの除去を許す、オンライン除去可能ナップサック問題を提案した。応用例として、ビッグデータを対象とした効率的なサンプリングが挙げられる。本研究ではオンライン除去可能ナップサック問題に対し、以下の2つの側面から研究を行ってきた。(1) 我々は、ナップサックとアイテムサイズをともに整数値とする場合を研究してきた。Iwama と Taketomi が解析した、本問題の難しさを表す指標であるところの競合比は、アイテムサイズが任意の実数値をとることを前提として導かれた。しかしそれでは、有限精度の有理数を扱う計算機上での性能評価とは乖離が生じる。我々はナップサックのサイズをパラメータとして固定した場合に対して、それぞれタイトな競合比を求めた。この成果を電子情報通信学会英文論文誌Aに論文投稿し、採録された。(2) 我々は、アイテムの除去に制約を課す問題を考察してきた。元の Iwama と Taketomi のオンライン除去可能ナップサック問題では、ナップサック内の任意のアイテムを除去することが許された。この問題の競合比は 1.618 である。これに対し我々は、キュー型ルールを設定する。すなわち、ナップサックに最も早く詰められたアイテムのみを除去できる、というルールである。我々はキュー型ルールのもと、問題の競合比がちょうど 2 であることを証明した。この成果を2022年度夏のLAシンポジウムにて発表した。

ナップサック問題は、単一のナップサックに、サイズの制約を守りつつ価値和が最大となるようにアイテムを詰める問題である。Iwama と Taketomi [ICALP 02]は派生問題として、アイテムが逐次与えられ、かつナップサックに一度詰めたアイテムの除去を許す、オンライン除去可能ナップサック問題を提案した。応用例として、ビッグデータを対象とした効率的なサンプリングが挙げられる。本研究ではオンライン除去可能ナップサック問題に対し、以下の2つの側面から研究を行ってきた。(1) 我々は、ナップサックとアイテムサイズをともに整数値とする場合を研究してきた。Iwama と Taketomi が解析した、本問題の難しさを表す指標であるところの競合比は、アイテムサイズが任意の実数値をとることを前提として導かれた。しかしそれでは、有限精度の有理数を扱う計算機上での性能評価とは乖離が生じる。我々はナップサックのサイズをパラメータとして固定した場合に対して、それぞれタイトな競合比を求めた。この成果を電子情報通信学会英文論文誌Aに論文投稿し、採録された。(2) 我々は、アイテムの除去に制約を課す問題を考察してきた。元の Iwama と Taketomi のオンライン除去可能ナップサック問題では、ナップサック内の任意のアイテムを除去することが許された。この問題の競合比は 1.618 である。これに対し我々は、キュー型ルールを設定する。すなわち、ナップサックに最も早く詰められたアイテムのみを除去できる、というルールである。我々はキュー型ルールのもと、問題の競合比がちょうど 2 であることを証明した。この成果を2022年度夏のLAシンポジウムにて発表した。