Two linear approximation algorithms for the subset-sum problem

Two linear approximation algorithms for the subset-sum problem

0.00 Avg rating0 Votes
Article ID: iaor2001407
Country: Netherlands
Volume: 120
Issue: 2
Start Page Number: 289
End Page Number: 296
Publication Date: Jan 2000
Journal: European Journal of Operational Research
Authors: , ,
Keywords: programming: linear
Abstract:

In this paper we study the subset-sum problem, 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.

Reviews

Required fields are marked *. Your email address will not be published.