SubsetSum@Home

[rebirther]

http://volunteer.cs.und.edu/subset_sum/

Team

The Subset Sum problem is described as follows: given a set of positive integers S and a target sum t, is there a subset of S whose sum is t? It is one of the well-know, so-called “hard” problems in computing. It's actually a very simple problem, and the computer program to solve it is not extremely complicated. What's hard about it is the running time – all known exact algorithms have running time that is proportional to an exponential function of the number of elements in the set (for worst-case instances of the problem).

Over the years, a large number of combinatorial problems have been shown to be in the same class as Subset Sum (called NP-complete problems). But, depending on how you measure the size of the problem instance, there is evidence that Subset Sum is actually an easier problem that most of the others in its class. The goal of this project is to strengthen the evidence that Subset Sum is an easier hard problem.

Suppose we have a set of n positive whole numbers S whose maximum number is m. We will define the ratio n/m to be the density of the set and denote the sum of all elements in the set as &#8721;S. If you look at the list of sums produced by subsets of S, you notice that very few sums are missing if S is dense enough. In fact, it appears that there is an exact density threshold beyond which no sums between m and half the sum of S will be missing. Our preliminary experiments have led to the following hypothesis: A set of positive integers with maximum element m and size n > floor(m/2)+1 has a subset whose sum is t for every t in the range m < t < &#8721;S &#8722; m.

So here's where you can help. So far, we haven't been able to prove the hypothesis above. If you want to be really helpful, you can send us a proof (or show us where to find one in the research literature), and the project will be done. But if you want to be slightly less helpful and have more fun, you can volunteer your computer as a worker to see how far we can extend the empirical evidence. You will also be helping us figure out better ways to apply distributed computing to combinatorial problems.

[odicin]

Nachricht von Travis bei DNA@Home. Siehts so aus als ob es hier bald losgeht:

We're starting to get video for wildlife@home, which should prove really interesting so it might be worth taking a look at that project over there. I'll also be starting to send out workunits for SubsetSum@Home by the end of the week (as we have a deadline for a conference and would like to have the project running by then). After SubsetSum@Home is up and sending out workunits, I'll be updating the client application here (to fix the checkpointing issue) and sending out some more workunits.

Until then, hopefully the videos we'll be putting up on wildlife@home will keep you interested, and the workunits at subsetsum@home will keep your computers busy. :)

[odicin]

Hi Everyone,

I've come up with what will hopefully be a good solution to the project unification. I've created a new project called Citizen Science Grid, which you can take a look at here (note it's very rough and i'm still working on a lot of the webpages to unify everything):

http://volunteer.cs.und.edu/csg/alpha/index.php

Since Wildlife@Home has been the most recently active project, I'm re-using the Wildlife@Home database for this project. Note that this project won't export statistics. Instead, credit earned by this project will be exported into the various sub projects.

So this means if you run Wildlife@Home only, you don't need to do anything. If you run any of the other projects, first make an account on Wildlife@Home (or on the Citizen Science Grid webpage) if you don't have one already.

I'm currently working on a webpage where you'll be able to link the account on Citizen Science Grid/Wildlife@Home to your accounts on DNA@Home or SubsetSum@Home. You'll need to enter in your user name and email for the account you want to link it to. Then when you generate credit it will be generated for that old account.

In a week or so I'm going to shut down the forums on SubsetSum@Home and DNA@Home, because they're going to just use the forum on Citizen Science Grid. That way all projects will be using the same forum.

Does that sound okay?

--Travis

I've created a page for linking your DNA@Home and SubsetSum@Home accounts here:

http://volunteer.cs.und.edu/csg/link_accounts.php

Your accounts need to have the same email address on here and the account you wish to link to. After you've linked accounts, any credit you generate for DNA@Home or SubsetSum@Home work units will be added to the project on those accounts. If you don't have an account there, your account here will be used to generate credit there.

From here on out, all the work units for Wildlife@Home, SubsetSum@Home and DNA@Home will be generated using the Citizen Science Grid scheduler, so you'll need to add it to BOINC manager: http://volunteer.cs.und.edu/csg

Let me know if you have any problems!