The Art Gallery Guardian

Subset sum of elements sum to \sigma


We assume the input of the subset sum problem is a sequence of n positive integers that sums to \sigma. We are interested if there is a subsequence sums to t.

In this case, the subset sum problem can be solved in O(\sigma \log^2 \sigma) time. In fact, it output all possible subset sums in the same running time.

Consider we partition the input into two subsequences, each have sum in between \sigma/4 and 3\sigma/4, and solve each recursively then take the Minkowski sum. One can analyze this and get O(\sigma \log^2 \sigma) running time. Notice if at some point, such partition cannot be found, then there is a side with a single huge element, and hence can be solved in constant time.

Posted by Chao Xu on 2015-07-20.
Tags: .