ナップサック問題に対する定数時間近似アルゴリズム  [in Japanese] Constant-time approximation algorithms for the knapsack problem  [in Japanese]

本稿ではナップサック問題に対する定数時間近似アルゴリズム,すなわち出力と最適解の絶対誤差がε以下となる確率が2/3以上である乱択アルゴリズムを示す.ただし,ここではアイテムの総価値は1に正規化されている.各アイテムをサンプリングする確率が各々の価値に比例する重み付きサンプリングを用いることで,ナップサック問題に対して計算時間がO(ε^<-4>logε^<-1>)である定数時間近似アルゴリズムを与える.更に部分和問題に対しては計算時間がO(ε^<-2>)である定数時間近似アルゴリズムを与える.更に,各アイテムが等確率でサンプリングされる一様サンプリングを用いた場合はΩ(n)回のサンプリングが必要であることも示した.

In this paper, we give constant-time approximation algorithms for the knapsack problem. A randomized algorithm is called an ε-approximation algorithm if it outputs the optimal value with an additive error ε with probability at least 2/3. Here, the total value of items is normalized to 1. By using weighted sampling, with which we can sample items with probability proportional to their values, we give an ε-approximation algorithm for the knapsack problem, which runs in O(ε^<-4>log ε^<-1>) time. We also give an ε-approximation algorithm for the subset sum problem, which runs in O(ε^<-2>) time. We also show that Ω(n) samplings are necessary if uniform sampling, which selects every item with uniform probability, is used.