Largest differencing method: Difference between revisions

Revision as of 11:35, 23 November 2020

Revision as of 19:43, 17 December 2020

Line 25:

* When there are at most 4 items, LDM returns the optimal partition.

*LDM always returns a partition in which 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> This is tight when there are 5 or more items.'''<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">{{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|authorlinkauthor-link=Brian Hayes (scientist)}}</ref>

=== Multi-way partitioning ===

Line 80:

* 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. In practice, with ''k''=2, problems of arbitrary size can be solved by CKK if the numbers have at most 12 [[Significant figures|significant digits]]; with ''k''=3, at most 6 significant digits.<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>

CKK can also run as an [[anytime algorithm]]: it finds the KK solution first, and then finds progressively better solutions as time allows (possibly requiring exponential time to reach optimality, for the worst instances).<ref>{{Cite journal|last=Korf|first=Richard E.|date=1998-12-01|title=A complete anytime algorithm for number partitioning|url=http://www.sciencedirect.com/science/article/pii/S0004370298000861|journal=Artificial Intelligence|language=en|volume=106|issue=2|pages=181–203|doi=10.1016/S0004-3702(98)00086-1|issn=0004-3702}}</ref>

== Previous mentions ==

An algorithm equivalent to the Karmarkar-Karp differencing heuristic is mentioned in ancient Jewish legal texts by [[Nachmanides]] and [[Joseph ibn Habib]]. The algorithm is used to combine different testimoines about the same loan.<ref>{{Cite journal|last=Ron Adin and Yuval Roichman|first=|date=2015|title=Combining witnesses: mathematical aspects|url=https://u.cs.biu.ac.il/~tsaban/Pdf/AdinRoichman.pdf|journal=BDD|language=Hebrewhe|publisher=[[Bar-Ilan University]]|volume=30|pages=7--20|via=}}</ref>

== References ==