Content deleted Content added
Erel Segal (talk | contribs) |
Erel Segal (talk | contribs) |
||
Line 1:
In [[computer science]], the '''largest differencing method''' is an algorithm for solving the [[partition problem]] and the [[multiway number partitioning]]. It is also called the '''Karmarkar–Karp algorithm''' after its inventors, [[Narendra Karmarkar]] and [[Richard M. Karp]].<ref>[[Narendra Karmarkar]] and [[Richard M. Karp]], "The differencing method of set partitioning", Tech report UCB/CSD 82/113, Computer science division, [[University of California, Berkeley]], 1982</ref> It is often abbreviated as '''LDM.<ref name=":2">{{cite journal|last1=Michiels|first1=Wil|last2=Korst|first2=Jan|last3=Aarts|first3=Emile|year=2003|title=Performance ratios for the Karmarkar–Karp differencing method|journal=Electronic Notes in Discrete Mathematics|volume=13|pages=71–75|citeseerx=10.1.1.107.1332|doi=10.1016/S1571-0653(04)00442-1}}</ref>''' <ref name=":1">{{Cite journal|last=Yakir|first=Benjamin|date=1996-02-01|title=The Differencing Algorithm LDM for Partitioning: A Proof of a Conjecture of Karmarkar and Karp|url=https://pubsonline.informs.org/doi/abs/10.1287/moor.21.1.85|journal=Mathematics of Operations Research|volume=21|issue=1|pages=85–99|doi=10.1287/moor.21.1.85|issn=0364-765X}}</ref>
== The algorithm ==
Line 13:
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.
The runtime complextiy of this algorithm is dominated by the step 1 (sorting), which takes O(''n'' log ''n'').
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:
Line 19:
* 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" />
* 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> ▼
===
For any ''k'' ≥ 2, The largest sum is at most <math>\frac{4}{3}-\frac{1}{3 k}</math> times the optimum.'''<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" />
== Implementation ==
| |||