|
In [[computer science]], '''Karmarkar–Karp number partitioning''' (is an algorithm for solving the [[partition problem]] and the [[multiway number partitioning]]. It is called 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 also called the '''largest differencing method''' '''(LDM).<ref>{{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>''') is<ref anname=":1">{{Cite algorithmjournal|last=Yakir|first=Benjamin|date=1996-02-01|title=The forDifferencing solvingAlgorithm theLDM [[partitionfor problem]]Partitioning: andA theProof [[multiwayof numbera partitioning]].Conjecture It is called after its inventors, [[Narendraof Karmarkar]] and [[Richard M. Karp]]|url=https://pubsonline.<ref>[[Narendra Karmarkar]] and [[Richard Minforms. Karp]], "The differencing method of set partitioning", Tech report UCBorg/CSD 82doi/113, Computer science division, [[Universityabs/10.1287/moor.21.1.85|journal=Mathematics of California,Operations Berkeley]], 1982Research|volume=21|issue=1|pages=85–99|doi=10.1287/moor.21.1.85|issn=0364-765X}}</ref>
== An approximateThe algorithm ==
The input to the algorithm is a set ''S'' of numbers, and a parameter ''k''. The required output is a partition of ''S'' into ''k'' subsets, such that the sums in the subsets are as nearly equal as possible. The main steps of the algorithm are:
For ''k''=2, step 2 operates as follows. It takes the two largest numbers, removes them from ''S'', and replaces them with their difference (this represents a decision to put each of these numbers in a different subset). It proceeds 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 2.
InThe theruntime secondcomplextiy phase,of thethis subsetsalgorithm areis reconstructeddominated by [[backtracking]].the Thestep runtime1 complextiy(sorting), of the approximate algorithm iswhich takes O(''n'' log ''n'').<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>
which can be backtracked to the 2-way partitions {3},{1}, then {4},{1,1}, then {4,7}, {1,8}, then {4,7,5}, {8,6}, where the sum-difference is 2. 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>. <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>
=== 3-way partitioning ===
|
