Content deleted Content added
Erel Segal (talk | contribs) |
Erel Segal (talk | contribs) |
||
Line 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>1+n^{-\Theta(\log(n)))}</math> . <ref name=":1" />
* When there are at most 4 items, LDM returns the optimal partition.
*LDM always returns a partition in which 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> This is tight when there are 5 or more items.'''<ref name=":2" />'''
| |||