講演抄録/キーワード |
講演名 |
2011-03-09 14:10
ナップサック問題に対する定数時間近似アルゴリズム 伊藤大雄・○清島 奨・吉田悠一(京大) COMP2010-51 |
抄録 |
(和) |
本稿ではナップサック問題に対する定数時間近似アルゴリズム,
すなわち出力と最適解の絶対誤差が$\epsilon$以下となる確率が$2/3$以上である乱択アルゴリズムを示す.ただし,ここではアイテムの総価値は$1$に正規化されている.各アイテムをサンプリングする確率が各々の価値に比例する重み付きサンプリングを用いることで,ナップサック問題に対して計算時間が$O(\epsilon^{-4}\log\epsilon^{-1})$である定数時間近似アルゴリズムを与える.更に部分和問題に対しては計算時間が$O(\epsilon^{-2})$である定数時間近似アルゴリズムを与える.更に,各アイテムが等確率でサンプリングされる一様サンプリングを用いた場合は$\Omega(n)$回のサンプリングが必要であることも示した. |
(英) |
In this paper, we give constant-time approximation algorithms
for the knapsack problem.
A randomized algorithm is called an $\epsilon$-approximation algorithm
if it outputs the optimal value with an additive error $\epsilon$ 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 $\epsilon$-approximation algorithm for the knapsack problem, which runs in $O(\epsilon^{-4}\log \epsilon^{-1})$ time. We also give an $\epsilon$-approximation algorithm for the subset sum problem, which runs in $O(\epsilon^{-2})$ time. We also show that $\Omega(n)$ samplings are necessary if uniform sampling, which selects every item with uniform probability, is used. |
キーワード |
(和) |
ナップサック問題 / 部分和問題 / 定数時間近似アルゴリズム / / / / / |
(英) |
knapsack problem / subset sum problem / constant-time approximation algorithm / / / / / |
文献情報 |
信学技報, vol. 110, no. 464, COMP2010-51, pp. 29-36, 2011年3月. |
資料番号 |
COMP2010-51 |
発行日 |
2011-03-02 (COMP) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
COMP2010-51 |