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 25 May 2010 05:58 hi all, I'm looking for a problem data set that can be fed to my algorithm and see how it compares with the known algorithms. Actually, mine are multiple algorithms and all of them work at the same time on a given problem, sharing the problem areas based their strengths. It is difficult to explain full algorithms here and it may not be worth talking about them unless I can test and see that these algorithms have a performance that is closer to that of known algorithms. However, I' can't find any specification for the reasonably large data set (how many values, value sizes, negatives are included etc) to be used as input. Also I don't know the time taken by the current algorithms to crack the same data sets. Has anybody has any pointers as to where I can find this info? Thanks a lot, -bheema
From: bheema s on 25 May 2010 07:01 May be I didn't mention the problem (except in the subject). Given a set of integers, it is the problem of finding a subset whose elements total up to a given value. -bheema On May 25, 2:58 pm, bheema s <bheem...(a)gmail.com> wrote: > hi all, > > I'm looking for a problem data set that can be fed to my algorithm and > see how it compares with the known algorithms. Actually, mine are > multiple algorithms and all of them work at the same time on a given > problem, sharing the problem areas based their strengths. It is > difficult to explain full algorithms here and it may not be worth > talking about them unless I can test and see that these algorithms > have a performance that is closer to that of known algorithms. > > However, I' can't find any specification for the reasonably large data > set (how many values, value sizes, negatives are included etc) to be > used as input. Also I don't know the time taken by the current > algorithms to crack the same data sets. Has anybody has any pointers > as to where I can find this info? > > Thanks a lot, > -bheema
From: Chip Eastham on 25 May 2010 10:36 On May 25, 7:01 am, bheema s <bheem...(a)gmail.com> wrote: > May be I didn't mention the problem (except in the subject). Given a > set of integers, it is the problem of finding a subset whose elements > total up to a given value. > > -bheema > > On May 25, 2:58 pm, bheema s <bheem...(a)gmail.com> wrote: > > > hi all, > > > I'm looking for a problem data set that can be fed to my algorithm and > > see how it compares with the known algorithms. Actually, mine are > > multiple algorithms and all of them work at the same time on a given > > problem, sharing the problem areas based their strengths. It is > > difficult to explain full algorithms here and it may not be worth > > talking about them unless I can test and see that these algorithms > > have a performance that is closer to that of known algorithms. > > > However, I' can't find any specification for the reasonably large data > > set (how many values, value sizes, negatives are included etc) to be > > used as input. Also I don't know the time taken by the current > > algorithms to crack the same data sets. Has anybody has any pointers > > as to where I can find this info? > > > Thanks a lot, > > -bheema > > [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. regards, chip
From: bheema s on 26 May 2010 05:08 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
From: Chip Eastham on 26 May 2010 11:03
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-08.pdf 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 |