Content deleted Content added
Use dash instead of hyphen |
Erel Segal (talk | contribs) No edit summary |
||
Line 32:
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.<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 ==
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=Hebrew|publisher=[[Bar-Ilan University]]|volume=30|pages=7--20|via=}}</ref>
== References ==
| |||