Name
Abstract | ||
|---|---|---|
In this paper we study the subset-sum problem (SSP), which is the problem of finding, given a set of n positive integers and a knapsack of capacity c, a subset the sum of which is closest to c without exceeding the value c. A short algorithm with worst-case guarantee 3/4 is introduced which outperforms Martello and Toth's 3/4 algorithm requiring a complexity time of O(n) instead of O(n2). The second linear time algorithm reaches a 4/5 worst-case performance ratio. Both bounds are shown to be tight. Computational results on randomly generated and deterministic test problems are reported. |
Year | DOI | Venue |
|---|---|---|
2000 | 10.1016/S0377-2217(99)00157-5 | European Journal of Operational Research |
Keywords | Field | DocType |
Subset-sum,Approximation algorithms,Worst-case performance | Integer,Partition problem,Knapsack problem,Time complexity,Criss-cross algorithm,Linear approximation,Approximation algorithm,Discrete mathematics,Subset sum problem,Combinatorics,Mathematical optimization,Algorithm,Mathematics | Journal |
Volume | Issue | ISSN |
120 | 2 | 0377-2217 |
Citations | PageRank | References |
10 | 0.63 | 4 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Hans Kellerer | 1 | 1098 | 99.56 |
| Renata Mansini | 2 | 574 | 43.10 |
| Maria Grazia Speranza | 3 | 1217 | 77.86 |