Largest differencing method: Difference between revisions

Revision as of 10:18, 19 November 2020

Revision as of 10:18, 19 November 2020

Line 1:

In [[computer science]], '''Karmarkar-KarpKarmarkar–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>

== An approximate algorithm ==

The '''largest differencing heuristic<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>''' (also called the '''Karmarkar-KarpKarmarkar–Karp heuristic''') sorts the numbers in descending order. For ''k''=2, it operates in two phases. In the first phase, 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, which is the sum-difference. 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>

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.

Line 29:

== An exact algorithm ==

The '''complete Karmarkar-KarpKarmarkar–Karp algorithm (CKK)''' finds an optimal solution in the following way. It constructs a tree of degree <math>k!</math>. Each level corresponds to a pair of numbers, and each of the <math>k!</math> branches corresponds to a different way to allocate them into the ''k'' sets. For example, with ''k''=2 there are two branches: in one branch the two largest numbers are replaced with their difference (corresponding to putting these numbers in different subsets), and in the other branch they are replaced with their sum (corresponding to putting them in the same subset). This algorithm finds the KK solution first, but then proceeds to find better solutions.

For ''k''=2, CKK runs substantially faster than the [[Greedy number partitioning|Complete Greedy Algorithm (CGA)]] on random instances. This is due to two reasons: when an equal partition does not exist, CKK often allows more trimming than CGA; and when an equal partition does exist, CKK often finds it much faster and thus allows earlier termination.<ref name=":0">{{Cite journal|last=Korf|first=Richard E.|date=1995-08-20|title=From approximate to optimal solutions: a case study of number partitioning|url=https://dl.acm.org/doi/abs/10.5555/1625855.1625890|journal=Proceedings of the 14th international joint conference on Artificial intelligence - Volume 1|series=IJCAI'95|___location=Montreal, Quebec, Canada|publisher=Morgan Kaufmann Publishers Inc.|volume=|pages=266–272|doi=|isbn=978-1-55860-363-9|via=}}</ref>