1
$\begingroup$

the partition problem (or number partitioning1) is the task of deciding whether a given multiset S of positive integers can be partitioned into two subsets S1 and S2 such that the sum of the numbers in S1 equals the sum of the numbers in S2.

There is a greedy algorithm for this problem:

One approach to the problem, imitating the way children choose teams for a game, is the greedy algorithm, which iterates through the numbers in descending order, assigning each of them to whichever subset has the smaller sum. This approach has a running time of O(n log n). This heuristic works well in practice when the numbers in the set are of about the same size as its cardinality or less, but it is not guaranteed to produce the best possible partition. For example, given the set S = {4, 5, 6, 7, 8} as input, this greedy algorithm would partition S into subsets {4, 5, 8} and {6, 7}; however, S has an exactly balanced partition into subsets {7, 8} and {4, 5, 6}.

But, I don't know how to prove "This heuristic works well in practice when the numbers in the set are of about the same size as its cardinality or less". Can anyone help?

Improve this question
$\endgroup$
2

2 Answers 2

Reset to default
3
$\begingroup$

There is nothing to prove about the statement you highlight. It is an empirical statement.

In order to have something to prove, you will need to formulate this claim formally in some way or another. There are many options, including average-case analysis, smoothed analysis, and restricted instances (which is what the statement points at). Until you have done so, it is impossible to prove or refute the statement.

The example given in your source shows that, in fact, the heuristic doesn't always succeed. Perhaps it gives a good approximation in some circumstances. The statement, unfortunately, doesn't hint at a provable claim which has any chance of being true.

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ You can, of course, perform experiments to validate the statement empirically. That is the closest you could get to "proof". $\endgroup$
    – Tom van der Zanden
    Sep 26, 2016 at 18:42
0
$\begingroup$

What you describe is just an approximate algorithm for the Job Shop problem (which is also NP-complete, reduced from Partition -- split a set of integers in two so that both add to the same value, the problem you describe) that can be shown has an approximation ratio of 2. See for example this set of slides for a proof and hints at refinements that get better approximation ratio.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.