Content deleted Content added
Erel Segal (talk | contribs) |
Erel Segal (talk | contribs) No edit summary |
||
Line 1:
In [[computer science]], '''Karmarkar–Karp number partitioning''' (also called the '''largest differencing method<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 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>
== An approximate 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:
# Sort the numbers in descending order.
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, 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. ▼
# Repeatedly replace numbers by their difference, until one number remains.
# Using [[backtracking]], compute the partition.
=== Two-way partitioning ===
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.
In the second phase, the subsets are reconstructed by [[backtracking]]. The runtime complextiy of the approximate algorithm is 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>
▲
=== 3-way partitioning ===
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" />
| |||