This paper describes a new approach for solving a large subproblem of the subset-sum problem. It is useful for solving other NP-hard integer programming problems. The limits and potential of this approach are investigated.
The approach yields an algorithm for solving the dense version of the subset-sum problem. It runs in time O(l log l), where l is the bound on the size of the elements. But for dense enough inputs and target numbers near the middle sum it runs in time O(m), where m is the number of elements. Consequently, it improves the previously best algorithms by at least one order of magnitude and sometimes by two.
The algorithm yields a characterization of the set of subset sums as a collection of arithmetic progressions with the same difference. This characterization is derived by elementary number theoretic and algorithmic techniques. Such a characterization was first obtained by using analytic number theory and yielded inferior algorithms.
Work partially supported by NSF Grants CCR-8814977 and CCR-9014605.