Name
Abstract | ||
|---|---|---|
In this paper, we give a constant-time approximation algorithm for the knapsack problem. Using weighted sampling, with which we can sample items with probability proportional to their profits, our algorithm runs with query complexity O (ε −4 logε −1), and it approximates the optimal profit with probability at least 2/3 up to error at most an ε -fraction of the total profit. For the subset sum problem, which is a special case of the knapsack problem, we can improve the query complexity to O (ε −1 logε −1). |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1007/978-3-642-29952-0_17 | TAMC |
Keywords | Field | DocType |
optimal profit,query complexity,special case,knapsack problem,constant-time approximation algorithm,sample item,weighted sampling,subset sum problem,total profit | Discrete mathematics,Approximation algorithm,Combinatorics,Subset sum problem,Change-making problem,Continuous knapsack problem,Cutting stock problem,Sampling (statistics),Knapsack problem,Polynomial-time approximation scheme,Mathematics | Conference |
Citations | PageRank | References |
3 | 0.42 | 13 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Hiro Ito | 1 | 290 | 39.95 |
| Susumu Kiyoshima | 2 | 24 | 4.03 |
| Yuichi Yoshida | 3 | 469 | 44.88 |