Content deleted Content added
Erel Segal (talk | contribs) |
Erel Segal (talk | contribs) |
||
Line 9:
=== Two-way partitioning ===
For ''k''=2, the main step (2) works as follows.
* Take the two largest numbers in ''S'', remove them from ''S'', and insert their difference (this represents a decision to put each of these numbers in a different subset).
Step 3 constructs the subsets in the partition by backtracking. The last step corresponds to {2},{}. Then 2 is replaced by 3 in one set and 1 in the other set: {3},{1}, then {4},{1,1}, then {4,7}, {1,8}, then {4,7,5}, {8,6}, where the sum-difference is 2. ▼
* Proceed in this way until a single number remains. This single number is the difference in sums between the two subsets.
For example, if S = {8,7,6,5,4}, then the resulting difference-sets are 6,5,4,1, then 4,1,1, then 3,1 then 2.
▲Step 3 constructs the subsets in the partition by backtracking. The last step corresponds to {2},{}. Then 2 is replaced by 3 in one set and 1 in the other set: {3},{1}, then {4},{1,1}, then {4,7}, {1,8}, then {4,7,5}, {8,6}, where the sum-difference is indeed 2.
The runtime complextiy of this algorithm is dominated by the step 1 (sorting), which takes O(''n'' log ''n'').
Line 17 ⟶ 22:
Note that this partition is not optimal: in the partition {8,7}, {6,5,4} the sum-difference is 0. However, there is evidence that it provides a "good" partition:
* If the numbers are uniformly distributed in [0,1], then the expected difference between the two sums is <math>n^{-\Theta(\log(n)))}</math>. This also implies that the expected ratio between the maximum sum and the optimal maximum sum is <math>n^{-\Theta(\log(n)))}</math>
* The largest sum is at most 7/6 times the optimum.<ref>{{Cite journal|last=Fischetti|first=Matteo|last2=Martello|first2=Silvano|date=1987-02-01|title=Worst-case analysis of the differencing method for the partition problem|url=https://doi.org/10.1007/BF02591687|journal=Mathematical Programming|language=en|volume=37|issue=1|pages=117–120|doi=10.1007/BF02591687|issn=1436-4646}}</ref>
*On random instances, this approximate algorithm performs much better than [[greedy number partitioning]]. However, it is still bad for instances where the numbers are exponential in the size of the set.<ref name="hayes">{{citation|last=Hayes|first=Brian|title=The Easiest Hard Problem|date=March–April 2002|magazine=[[American Scientist]]|volume=90|issue=2|pages=113–117|publisher=Sigma Xi, The Scientific Research Society|jstor=27857621|authorlink=Brian Hayes (scientist)}}</ref>
=== Multi-way partitioning ===
For any ''k'' ≥ 2,
* Initially, for each number ''i'' in ''S'', construct a ''k''-tuple of subsets, in which one subset is {''i''} and the other ''k''-1 subsets are empty.
* In each iteration, select two ''k''-tuples ''A'' and ''B'' in which the difference between the maximum and minimum sum is largest, and combine them in reverse order of sizes, i.e.: smallest subset in ''A'' with largest subset in ''B'', second-smallest in ''A'' with second-largest in ''B'', etc.
* Proceed in this way until a single partition remains.
Examples:
* If S = {8,7,6,5,4} and ''k''=2, then the initial partitions are ({8},{}), ({7},{}), ({6},{}), ({5},{}), ({4},{}). After the first step we get ({6},{}), ({5},{}), ({4},{}), ({8},{7}). Then ({4},{}), ({8},{7}), ({6},{5}). Then ({4,7},{8}), ({6},{5}), and finally ({4,7,5},{8,6}), where the sum-difference is 2; this is the same partition as described above.
* If S = {8,7,6,5,4} and ''k''=3, then the initial partitions are ({8},{},{}), ({7},{},{}), ({6},{},{}), ({5},{},{}), ({4},{},{}). After the first step we get ({8},{7},{}), ({6},{},{}), ({5},{},{}), ({4},{},{}). Then ({5},{},{}), ({4},{},{}), ({8},{7},{6}). Then ({5},{4},{}), ({8},{7},{6}), and finally ({5,6},{4,7},{8}), where the sum-difference is 3.
* If S = {5,5,5,4,4,3,3,1} and ''k''=3, then after 7 iterations we get the partition ({5,5},{3,3,4},{1,4,5}).'''<ref name=":2" />'''
There is evidence for the good performance of LDM:'''<ref name=":2" />'''
* Simulation experiments show that, when the numbers are uniformly random in [0,1], LDM always performs better (i.e., produces a partition with a smaller largest sum) than [[greedy number partitioning]]. It performs better than the [[multifit algorithm]] when the number of items ''n'' is sufficiently large. When the numbers are uniformly random in [''o'', ''o''+1], from some ''o''>0, the performance of LDM remains stable, while the performance of multifit becomes worse as ''o'' increases. For ''o''>0.2, LDM performs better.
* In all cases, the largest sum in the LDM partition is at most <math>\frac{4}{3}-\frac{1}{3 k}</math> times the optimum, and there are instances in which it is at least <math>\frac{4}{3}-\frac{1}{3 (k-1)}</math> times the optimum.'''<ref name=":2" />'''
== Implementation ==
| |||