✦ LIBER ✦

An efficient fully polynomial approximation scheme for the Subset-Sum Problem

✍ Scribed by Hans Kellerer; Renata Mansini; Ulrich Pferschy; Maria Grazia Speranza

Publisher: Elsevier Science
Year: 2003
Tongue: English
Weight: 238 KB
Volume: 66
Category: Article
ISSN: 0022-0000
DOI: 10.1016/s0022-0000(03)00006-0

No coin nor oath required. For personal study only.

✦ Synopsis

Given a set of n positive integers and a knapsack of capacity c; the Subset-Sum Problem is to find a subset the sum of which is closest to c without exceeding the value c: In this paper we present a fully polynomial approximation scheme which solves the Subset-Sum Problem with accuracy e in time Oðminfn Á 1=e; n þ 1=e 2 logð1=eÞgÞ and space Oðn þ 1=eÞ: This scheme has a better time and space complexity than previously known approximation schemes. Moreover, the scheme always finds the optimal solution if it is smaller than ð1 À eÞc: Computational results show that the scheme efficiently solves instances with up to 5000 items with a guaranteed relative error smaller than 1/1000.

📜 SIMILAR VOLUMES

A polynomial approximation scheme for th

A polynomial approximation scheme for the subset sum problem

✍ Nei Yoshihiro Soma; Alan Solon Ivor Zinober; Horacio Hideki Yanasse; Peter John 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 462 KB

Worst-case analysis of an approximation

Worst-case analysis of an approximation scheme for the subset-sum problem

✍ Matteo Fischetti 📂 Article 📅 1986 🏛 Elsevier Science 🌐 English ⚖ 150 KB

A fully polynomial approximation scheme

A fully polynomial approximation scheme for the total tardiness problem

✍ E.L. Lawler 📂 Article 📅 1982 🏛 Elsevier Science 🌐 English ⚖ 169 KB

Efficient Approximation Algorithms for t

Efficient Approximation Algorithms for the Subset-Sums Equality Problem

✍ Cristina Bazgan; Miklos Santha; Zsolt Tuza 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 117 KB

A fully polynomial bicriteria approximat

A fully polynomial bicriteria approximation scheme for the constrained spanning tree problem

✍ Sung-Pil Hong; Sung-Jin Chung; Bum Hwan Park 📂 Article 📅 2004 🏛 Elsevier Science 🌐 English ⚖ 213 KB

We propose a fully polynomial bicriteria approximation scheme for the constrained spanning tree problem. First, an exact pseudo-polynomial algorithm is developed based on a two-variable extension of the well-known matrix-tree theorem. The scaling and approximate binary search techniques are then uti

An asymptotic fully polynomial time appr

An asymptotic fully polynomial time approximation scheme for bin covering

✍ Klaus Jansen; Roberto Solis-Oba 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 175 KB

In the bin covering problem there is a group L = (a1; : : : ; an) of items with sizes s(ai) ∈ (0; 1), and the goal is to ÿnd a packing of the items into bins to maximize the number of bins that receive items of total size at least 1. This is a dual problem to the classical bin packing problem. In th