Largest differencing method: Difference between revisions

Revision as of 15:20, 19 November 2020

Revision as of 17:29, 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" />

* TheWhen there are at most 4 items, LDM returns the optimal partition. Otherwise, LDM 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>

Line 42:

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

*Let ''f*'' be the optimal largest sum. If all numbers are larger than ''f''*/3, then LDM returns the optimal solution. Otherwise, LDM returns a solution in which the difference between largest and smallest sum is at most the largest number which is at most ''f''*/3.

* 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" />'''

*When there are at most ''k''+2 items, LDM is optimal.

*When the number of items ''n'' is between ''k''+2 and 2''k'', the largest sum in the LDM partition is at most <math>\frac{4}{3}-\frac{1}{3 (n-k-1)}</math> times the optimum,

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