Content deleted Content added
TheMathCat (talk | contribs) m wikilink |
Citation bot (talk | contribs) Removed proxy/dead URL that duplicated identifier. | Use this bot. Report bugs. | Suggested by Corvus florensis | #UCB_webform 460/2500 |
||
Line 102:
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
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>
| |||