𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Probabilistic analysis of the subset-sum problem

✍ Scribed by Gianfranco D'Atri; Claude Puech

Publisher
Elsevier Science
Year
1982
Tongue
English
Weight
285 KB
Volume
4
Category
Article
ISSN
0166-218X

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

On the equal-subset-sum problem
On the equal-subset-sum problem
✍ Gerhard J. Woeginger; Zhongliang Yu πŸ“‚ Article πŸ“… 1992 πŸ› Elsevier Science 🌐 English βš– 339 KB
On variations of the subset sum problem
On variations of the subset sum problem
✍ J.L. RamΓ­rez AlfonsΓ­n πŸ“‚ Article πŸ“… 1998 πŸ› Elsevier Science 🌐 English βš– 371 KB

In the well-known Subset Sum Problem, we are given positive integers a,, , a, and t and are to determine if some subset of the ai sums to t. We investigate the boundary between easy and hard variations of this problem. In particular, we consider the cases where the sequence 'A,~ .L' a,, \_\_\_ ,an i

An efficient fully polynomial approximat
An efficient fully polynomial approximation scheme for the Subset-Sum Problem
✍ Hans Kellerer; Renata Mansini; Ulrich Pferschy; Maria Grazia Speranza πŸ“‚ Article πŸ“… 2003 πŸ› Elsevier Science 🌐 English βš– 238 KB

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Γ°m