Subset-sum problem with different summands. (English) Zbl 0701.90068

Freiman, G. A.

Combinatorics, graph theory, and computing, Proc. 20th Southeast Conf., Boca Raton/FL (USA) 1989, Congr. Numerantium 70, 207-215 (1990).

[For the entire collection see Zbl 0688.00002.]
The author proposes a linear time algorithm for solving the following subset sum problem \[ \max \sum a_ ix_ i\quad if\quad \sum^{m}_{i=1}a_ ix_ i\leq n,\quad x_ i\in \{0,1\} \] with relatively small summands bounded by the value \(\ell =O(m^{3/2}\log^{-2}m)\). The algorithm is based on the following theorem from additive number theory: \[ if\quad \#\{a| \quad a\in A,\quad a\equiv r(mod q)\}\leq m-\ell^{2/3} \] then the set of values of the subset sum functional contains an order 1/2 \((\sum a^ 2_ i)^{1/2}\) of consecutive integers.

Reviewer: M.Frumkin

MSC:

90C10

Integer programming

Keywords:

linear time algorithm; subset sum problem

Citations:

Zbl 0688.00002