A Fast Approximation Algorithm For The Subset-Sum Problem

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 ∈ is solved in O(min(n/∈, n + 1/∈ 3 )) t...

Full description

Saved in:
Bibliographic Details
Published in:INFOR. Information systems and operational research 1994-08, Vol.32 (3), p.143-148
Main Authors: Gens, George, Levner, Eugene
Format: Article
Language:English
Subjects:
Algorithms
Approximation
combinatorial algorithms
Discrete optimization
Dynamic programming
Knapsack problem
Optimization algorithms
Studies
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 ∈ is solved in O(min(n/∈, n + 1/∈ 3 )) time and O(min(n/∈, n + 1/∈ 2 )) space.
ISSN:0315-5986
1916-0615
DOI:10.1080/03155986.1994.11732245