Content deleted Content added
m Open access bot: doi added to citation with #oabot. |
|||
Line 92:
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.|pages=266–272|isbn=978-1-55860-363-9}}</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|doi-access=free}}</ref>
Combining CKK with the balanced-LDM algorithm (BLDM) yields a complete [[anytime algorithm]] for solving the [[balanced partition problem]].<ref>{{cite arXiv|last=Mertens|first=Stephan|date=1999-03-11|title=A complete anytime algorithm for balanced number partitioning|eprint=cs/9903011}}</ref>
| |||