Advanced search

Message boards : Science and Theory : Set Analysis Progress

Author Message
Travis Desell
Volunteer moderator
Project administrator
Project developer
Project scientist
Send message
Joined: 16 Jan 12
Posts: 1812
Combined Credit: 23,472,548
DNA@Home: 293,563
SubsetSum@Home: 349,212
Wildlife@Home: 22,829,774
Wildlife@Home Watched: 212,926s
Wildlife@Home Events: 51
Climate Tweets: 21
Images Observed: 755

              
Message 2981 - Posted: 8 Aug 2014, 3:33:02 UTC
Last modified: 29 Oct 2014, 2:04:56 UTC

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.

mzieg
Send message
Joined: 17 Apr 16
Posts: 1
Combined Credit: 580,173
DNA@Home: 22,398
SubsetSum@Home: 133,222
Wildlife@Home: 424,553
Wildlife@Home Watched: 0s
Wildlife@Home Events: 0
Climate Tweets: 0
Images Observed: 0

      
Message 6199 - Posted: 18 Apr 2016, 2:21:37 UTC - in response to Message 2981.
Last modified: 18 Apr 2016, 2:24:40 UTC

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 :-(

Eelco
Send 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
Message 6219 - Posted: 29 Apr 2016, 9:48:16 UTC
Last modified: 29 Apr 2016, 9:49:32 UTC

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 H
Send 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

    
Message 6222 - Posted: 2 May 2016, 9:02:24 UTC

Very good video explaining SSS problem:

https://www.youtube.com/watch?v=s6FhG--P7z0

Robert H
Send 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

    
Message 6223 - Posted: 2 May 2016, 9:44:42 UTC

Here is another very good video explaining SSS:

https://www.youtube.com/watch?v=zKwwjAkaXLI

Eelco
Send 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
Message 6241 - Posted: 15 May 2016, 17:46:14 UTC - in response to Message 6219.
Last modified: 15 May 2016, 17:51:22 UTC

Robert H
Send 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

    
Message 6305 - Posted: 11 Jun 2016, 8:29:41 UTC

Is the SSS algorithm always so called backtracking?

Robert H
Send 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

    
Message 6316 - Posted: 15 Jun 2016, 1:22:37 UTC
Last modified: 15 Jun 2016, 1:23:19 UTC

Are we moving forward?

The Max value is still 54 and Subset size is still 29

Robert H
Send 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

    
Message 6339 - Posted: 17 Jun 2016, 22:25:09 UTC
Last modified: 17 Jun 2016, 22:30:27 UTC

@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


Post to thread

Message boards : Science and Theory : Set Analysis Progress