Title :
Empirical support for the high-density subset sum decision threshold
Author :
O´Neil, T.E. ; Desell, T.
Author_Institution :
Department of Computer Science University of North Dakota Grand Forks, ND 58202-9015
Abstract :
This article describes several properties of the random problem space for the Subset Sum problem, derived both empirically and analytically. Empirical results support the conjecture that Subset Sum instances always have a solution when the input set S is a set of n elements with a maximum value of m, the target sum t is between m and the sum of the smallest n − 1 elements of S, and n ≥ ⌊m/2⌋ + 1. While the proof of this conjecture remains an open problem, exhaustive enumeration of problem instances has resulted in no counterexamples for values of m ≤ 49. Sequential processing was used to generate the empirical data for values up to m = 40. The SubsetSum@Home volunteer computing project reproduced the results of the sequential code and extended the enumeration beyond m = 49.
Keywords :
Computer applications; Conferences; Distributed processing; Dynamic programming; Heuristic algorithms; Time complexity;
Conference_Titel :
Information Theory (CWIT), 2015 IEEE 14th Canadian Workshop on
Conference_Location :
St. John´s, NL, Canada
DOI :
10.1109/CWIT.2015.7255176