Subset sum problem
in [Math]
|
Prev: Fornax, Columbia, Canes-Major Voids Chapt 11, Space is EM; magnet & iron filings Experiment #109; ATOM TOTALITY
Next: TWO BILLION ABSOLUTLY CORRECT PLACED PRIME NUMBERS FROM HOPE RESEARCH
From: bheema s on 27 May 2010 06:51 On May 26, 8:03 pm, Chip Eastham <hardm...(a)gmail.com> wrote: > On May 26, 5:08 am, bheema s <bheem...(a)gmail.com> wrote: > > > > > On May 25, 7:36 pm, Chip Eastham <hardm...(a)gmail.com> wrote: > > > > [SUBSET_SUM: Data for the Subset Sum Problem]http://people.sc.fsu.edu/~burkardt/datasets/subset_sum/subset_sum.html > > > > Distributed under the GNU LGPL License. > > > Thanks chip! I looked at these earlier and found them to be too > > trivial. I'm looking for larger data sets, where the existing > > algorithms would have spent significant amount of time (atleast > > minutes) in solving. > > > I'm fine with non-specific data sets also, such as, for example, "Any > > 100 random positive integers, each 20 decimal digits long, should take > > approximately 10 minutes to solve for target sum of half of their > > total sum" etc. This would help me in understanding where my algorithm > > stands. > > > Thanks again for the links. > > -venkat > > You might be interested in this paper by D. Pisinger: > > [Where are the hard knapsack problems? (2003)]http://www.diku.dk/OLD/publikationer/tekniske.rapporter/rapporter/03-... > > Subset sum problems there are considered as a special > case of knapsack problems, but one which is not "easy" > to solve (with one exception described by the author). > > He gives a "recipe" for generating the sorts of large > test cases on which he reports (cf. Sec. 3 Computational > Experiments). > > regards, chip Thanks a lot! This one has some info I'm looking for.
From: bheema s on 31 May 2010 03:16
On May 26, 8:03 pm, Chip Eastham <hardm...(a)gmail.com> wrote: > On May 26, 5:08 am, bheema s <bheem...(a)gmail.com> wrote: > > > > > On May 25, 7:36 pm, Chip Eastham <hardm...(a)gmail.com> wrote: > > > > [SUBSET_SUM: Data for the Subset Sum Problem]http://people.sc.fsu.edu/~burkardt/datasets/subset_sum/subset_sum.html > > > > Distributed under the GNU LGPL License. > > > Thanks chip! I looked at these earlier and found them to be too > > trivial. I'm looking for larger data sets, where the existing > > algorithms would have spent significant amount of time (atleast > > minutes) in solving. > > > I'm fine with non-specific data sets also, such as, for example, "Any > > 100 random positive integers, each 20 decimal digits long, should take > > approximately 10 minutes to solve for target sum of half of their > > total sum" etc. This would help me in understanding where my algorithm > > stands. > > > Thanks again for the links. > > -venkat > > You might be interested in this paper by D. Pisinger: > > [Where are the hard knapsack problems? (2003)]http://www.diku.dk/OLD/publikationer/tekniske.rapporter/rapporter/03-... > > Subset sum problems there are considered as a special > case of knapsack problems, but one which is not "easy" > to solve (with one exception described by the author). > > He gives a "recipe" for generating the sorts of large > test cases on which he reports (cf. Sec. 3 Computational > Experiments). > > regards, chip Did some more search for the data and results. Pisinger's paper does have some data but not very specific to subset problem. Also his data sets seem smaller compared what I have used. While I would again look into his pages for finding out more info and code, I would like to present my results: My Data set: Data: 200 random positive integers uniformly distributed between one billion and 2 billion. Target sum: A random integer equal to about 140 billions Result: The worst case so far took about 40 seconds finding about 120 to 140 elements summing to exact target, on a 32-bit PC (4gb mem) running WinXP. I ran the tests for several other random target sums, but 40 sec is the worst case so far. I would like to request your comments on the results. Thanks a lot for your time!! -b |