Content deleted Content added
Erel Segal (talk | contribs) |
Erel Segal (talk | contribs) Tags: nowiki added Visual edit |
||
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 digit]]<nowiki/>s; 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>
== Previous mentions ==
| |||