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?
-
5$\begingroup$ You can't prove that "This heuristic works well in practice" because that is not a statement of mathematics, so it is not accessible to proof. $\endgroup$David Richerby– David Richerby2016年09月26日 08:53:25 +00:00Commented Sep 26, 2016 at 8:53
-
1$\begingroup$ Cross-posted: stackoverflow.com/q/39693921/781723, cs.stackexchange.com/q/63882/755. Please do not post the same question on multiple sites. Each community should have an honest shot at answering without anybody's time being wasted. $\endgroup$D.W.– D.W. ♦2017年02月10日 23:23:50 +00:00Commented Feb 10, 2017 at 23:23
2 Answers 2
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.
-
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– Tom van der Zanden2016年09月26日 18:42:10 +00:00Commented Sep 26, 2016 at 18:42
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.