A fast approximation algorithm for the subset-sum problem

A fast approximation algorithm for the subset-sum problem

0.00 Avg rating—0 Votes
Article ID: iaor19942398
Country: Canada
Volume: 32
Issue: 3
Start Page Number: 143
End Page Number: 148
Publication Date: Aug 1994
Journal: INFOR
Authors: ,
Keywords: allocation: resources, combinatorial analysis
Abstract:

A new fully polynomial approximation scheme for the subset-sum problem is presented. This algorithm yields better time and space complexity bounds, and also tends to improve the practicability of the procedure. The subset-sum problem, for n items and accuracy e is solved in O(min(n/e, n+1/e3)) time and O(min(n/e, n+1/e2)) space.

Reviews

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