𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On variations of the subset sum problem

✍ Scribed by J.L. Ramírez Alfonsín

Publisher
Elsevier Science
Year
1998
Tongue
English
Weight
371 KB
Volume
81
Category
Article
ISSN
0166-218X

No coin nor oath required. For personal study only.

✦ Synopsis

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 is an arirnmeric progression, 8 chain or supermcredsmg and -w'here the ai may be replicated. We also consider related problems.

📜 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
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