Largest differencing method: Difference between revisions

Revision as of 17:29, 19 November 2020

Revision as of 17:30, 19 November 2020

Line 23:

* 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> . <ref name=":1" />

* When there are at most 4 items, LDM returns the optimal partition.
*LDM Otherwise, LDMalways 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" />'''

*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>