Paper Info
Title
Empirical support for the high-density subset sum decision threshold
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.
Year
DOI
Venue
2015
10.1109/CWIT.2015.7255176
2015 IEEE 14th Canadian Workshop on Information Theory (CWIT)
Keywords
Field
DocType
high-density subset sum decision threshold,random problem space,subset sum problem,sequential processing,SubsetSum@Home volunteer computing project
Partition problem,Discrete mathematics,Dynamic programming,Subset sum problem,Combinatorics,Open problem,Enumeration,Counterexample,Time complexity,Conjecture,Mathematics
Conference
Citations 
PageRank 
References 
0
0.34
13
Authors
2
Name
Order
Citations
PageRank
Thomas O'Neil100.34
Travis Desell211618.56