Set Analysis Progress

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: 1813 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: 26 Images Observed: 774	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.
	ID: 2981 · Rating: 0 · rate: / Reply Quote

mzieg Send 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	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 :-(
	ID: 6199 · Rating: 0 · rate: / Reply Quote

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 ____________
	ID: 6219 · Rating: 0 · rate: / Reply Quote

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
	ID: 6222 · Rating: 0 · rate: / Reply Quote

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
	ID: 6223 · Rating: 0 · rate: / Reply Quote

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

	ID: 6241 · Rating: 0 · rate: / Reply Quote

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?
	ID: 6305 · Rating: 0 · rate: / Reply Quote

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
	ID: 6316 · Rating: 0 · rate: / Reply Quote

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
	ID: 6339 · Rating: 0 · rate: / Reply Quote

Post to thread

Message boards : Science and Theory : Set Analysis Progress