Author |
Message |
Travis DesellVolunteer moderator Project administrator Project developer Project scientist Send message
Joined: 16 Jan 12 Posts: 1812 Combined Credit: 23,514,257 DNA@Home: 293,563 SubsetSum@Home: 349,212 Wildlife@Home: 22,871,482 Wildlife@Home Watched: 212,926s Wildlife@Home Events: 51 Climate Tweets: 21 Images Observed: 755
 |
Here is the progress we have so far of evaluated sets for given M (maximum set value) and N (set size).
But first, a little information on the format of the output. The first number is the iteration of the set. The numbers between the square brackets [] are the elements of the set. The program calculates the sets using arrays of binary numbers, and they go from right to left (not left to right). If there is a 0, then the set cannot generate that sum, and if there is a 1 it can.
So lets take 8 choose 5. In this case, a 0 on the far left means that any combination of the numbers in the set cannot generate the sum 32 (where the sums gets larger there will be longer bit strings). So the output says the set on the first line, [ 1 2 3 4 8], can generate every sum from 18 to 1. For the conjecture, we're interested in the sums from 10 to 8 (inclusive), and these are highlighted in green. Sets 9, 19 and 23 cannot generate all those central sums -- and the missing sums are highlighted in red. For set 9, it cannot generate the sum 12, set 19 cannot generate the sums 10 and 17, and set 23 cannot generate the sum 12. Ie., no combination of the sets elements can be added together to get that number.
As the number of sets evaluated increases exponentially as M and N increase, we'll only be printing out the failed sets (those are the ones we're interested anyways as we hope more information on these will help us prove the conjecture).
An automated php script generates the progress about the set sums, and can be found here: http://volunteer.cs.und.edu/csg/subset_sum/progress.php. This link is also on the front page of the project now, but this can be used for discussion of the progress. |
|
|
mziegSend message
Joined: 17 Apr 16 Posts: 1 Combined Credit: 591,854 DNA@Home: 22,398 SubsetSum@Home: 133,222 Wildlife@Home: 436,234 Wildlife@Home Watched: 0s Wildlife@Home Events: 0 Climate Tweets: 0 Images Observed: 0
 |
Hi,
I have a kind of stupid question. What is SubsetSum@Home trying to prove or discover? I understand the concept of the Subset problem from Wikipedia, I'm just not sure what the distributed work units are contributing toward. Do you have a new heuristic which you believe will probabilistically provide a better-than-current approximated result in fewer iterations than standard algorithms, whose performance must be demonstrated against a very large number of datasets? Are you just running different algorithms against one another to generate a table of comparative effectiveness against different types and sizes of input sets?
Just curious, and apologies for not seeing this on the main pages -- I'm sure it's there somewhere.
[UPDATE] found the answer, but don't seem able to delete the post :-( |
|
|
EelcoSend message
Joined: 27 Apr 16 Posts: 2 Combined Credit: 5,374 DNA@Home: 0 SubsetSum@Home: 5,374 Wildlife@Home: 0 Wildlife@Home Watched: 0s Wildlife@Home Events: 0 Climate Tweets: 0 Images Observed: 0
|
In the conjecture this is the hypothesis:
A set of positive integers with maximum element m and size n > floor(m/2)+1 has a subset with sum is t for every t in the range m < t < ∑S − m.
But studying the progress I see that for the range of t, "m" and "∑S − m" are included. And why not exclude the usage of same integer values?
So i.m.o. the hypothesis could better be:
A set of different positive integers including maximum element m (> 2) and size n (> floor(m/2)+1) has a subset whose sum is t for every t in the range m <= t <= ∑S − m.
And studying the results furthermore, why not extra also formulate this bold hypothesis :)
-->
There are 2 sets of positive different integers including maximum even element m (> 9) and size (m/2)+1, that have no subset with sum t for 2 values t in the range m <= t <= ∑S – m :
Set 1: [1 2 (m/2)+2 .. m], t = m + 4 and t = ∑S – m – 4
Set 2: [1 (m/2)+1 .. m], t = m + 2 and t = ∑S – m – 2
____________
|
|
|
Robert HSend message
Joined: 27 Oct 14 Posts: 38 Combined Credit: 251,816 DNA@Home: 31,083 SubsetSum@Home: 220,734 Wildlife@Home: 0 Wildlife@Home Watched: 0s Wildlife@Home Events: 0 Climate Tweets: 0 Images Observed: 0
 |
Very good video explaining SSS problem:
https://www.youtube.com/watch?v=s6FhG--P7z0 |
|
|
Robert HSend message
Joined: 27 Oct 14 Posts: 38 Combined Credit: 251,816 DNA@Home: 31,083 SubsetSum@Home: 220,734 Wildlife@Home: 0 Wildlife@Home Watched: 0s Wildlife@Home Events: 0 Climate Tweets: 0 Images Observed: 0
 |
Here is another very good video explaining SSS:
https://www.youtube.com/watch?v=zKwwjAkaXLI |
|
|
EelcoSend message
Joined: 27 Apr 16 Posts: 2 Combined Credit: 5,374 DNA@Home: 0 SubsetSum@Home: 5,374 Wildlife@Home: 0 Wildlife@Home Watched: 0s Wildlife@Home Events: 0 Climate Tweets: 0 Images Observed: 0
|
|
|
|
Robert HSend message
Joined: 27 Oct 14 Posts: 38 Combined Credit: 251,816 DNA@Home: 31,083 SubsetSum@Home: 220,734 Wildlife@Home: 0 Wildlife@Home Watched: 0s Wildlife@Home Events: 0 Climate Tweets: 0 Images Observed: 0
 |
Is the SSS algorithm always so called backtracking? |
|
|
Robert HSend message
Joined: 27 Oct 14 Posts: 38 Combined Credit: 251,816 DNA@Home: 31,083 SubsetSum@Home: 220,734 Wildlife@Home: 0 Wildlife@Home Watched: 0s Wildlife@Home Events: 0 Climate Tweets: 0 Images Observed: 0
 |
Are we moving forward?
The Max value is still 54 and Subset size is still 29 |
|
|
Robert HSend message
Joined: 27 Oct 14 Posts: 38 Combined Credit: 251,816 DNA@Home: 31,083 SubsetSum@Home: 220,734 Wildlife@Home: 0 Wildlife@Home Watched: 0s Wildlife@Home Events: 0 Climate Tweets: 0 Images Observed: 0
 |
@Travis:
I am wondering about these 2 subsets in the list:
53 28 216679 216687 -216686 0
54 27 441691 441688 -440767 19287
How come it says errored -216686 and -440767 when it says nowhere else!?
Are they really correct?
/Robert |
|
|