Largest differencing method: Difference between revisions

Revision as of 06:52, 20 November 2020

Revision as of 07:22, 20 November 2020

Line 75:

== An exact algorithm ==

The '''complete Karmarkar–Karp algorithm (CKK)''' finds an optimal solution by constructing a tree of degree <math>k!</math>.

The '''complete Karmarkar–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.

* In the case ''k''=2, each level corresponds to a pair of numbers, and the two branches correspond to taking their difference (i.e. putting them in different sets), or taking their sum (i.e. putting them in the same set).

* For general ''k'', each level corresponds to a pair of ''k''-tuples, and each of the <math>k!</math> branches corresponds to a different way of combining the subsets in these tuples.

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. Korf reports that CKK can optimally partition 40 15-digit double-precision numbers in about 3 hours, while CGA requires about 9 hours.<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>