Content deleted Content added
Correct example of k=3 and S={1,3,3,4,4,5,5} to match information in cited page (http://alexandria.tue.nl/extra1/wskrap/publichtml/200217.pdf). |
Citation bot (talk | contribs) Alter: journal, pages. Add: authors 1-1. Removed parameters. Formatted dashes. Some additions/deletions were parameter name changes. | Use this bot. Report bugs. | Suggested by SemperIocundus | #UCB_webform |
||
Line 24:
* 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>1+n^{-\Theta(\log(n)))}</math> . <ref name=":1" />
* 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|
*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|author-link=Brian Hayes (scientist)}}</ref>
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
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 testimonies about the same loan.<ref>{{Cite journal|last=Ron Adin and Yuval Roichman|date=2015|title=Combining witnesses: mathematical aspects|url=https://u.cs.biu.ac.il/~tsaban/Pdf/AdinRoichman.pdf|journal=BDD|language=he|publisher=[[Bar-Ilan University]]|volume=30|pages=
== References ==
| |||