Lecture Notes for CS 512, Algorithm Design

29 March 2000, Subset Sums

1. Given an set of positive integers S and a postitive integer t, does there exist a subset of S that sums to t

   1. start with the list L = <0>

   2. copy L to L'

   3. for the next element s of S, add s to every element of L'

   4. merge L and L', skipping elements larger than t

2. this algorithm is exponential, and NP complete; is there an approximation

3. trim the list by having near-by elements clumped together by the trim parameter d: (1 - d)y <= z <= y

   1. for example, <10, 11, 12, 15, 20, 21, 22, 23, 24 29> trims to <10, 12, 15, 20, 23 29> when d = 0.1

   2. does it reduce the list size

      1. successive elements differ by 1/(1 - d)

      2. there can be at most log 1/(1 - d) t <= (log t)/d

This page last modified on 3 April 2000.