Content deleted Content added
Erel Segal (talk | contribs) |
Erel Segal (talk | contribs) |
||
Line 51:
== Balanced two-way partitioning{{Anchor|balanced}} ==
Several variants of LDM were developed for the
'''PDM (Paired Differencing Method)''' works as follows.<ref>{{Cite journal|last=Lueker|first=George S|date=1987-12-01|title=A note on the average-case behavior of a simple differencing method for partitioning|url=https://www.sciencedirect.com/science/article/pii/0167637787900447|journal=Operations Research Letters|language=en|volume=6|issue=6|pages=285–287|doi=10.1016/0167-6377(87)90044-7|issn=0167-6377}}</ref>
Line 108:
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>
Combining CKK with the balanced-LDM algorithm (BLDM) yields a complete [[anytime algorithm]] for solving the [[balanced partition problem]].<ref>{{Cite journal|last=Mertens|first=Stephan|date=1999-03-11|title=A complete anytime algorithm for balanced number partitioning|url=http://arxiv.org/abs/cs/9903011|journal=arXiv:cs/9903011}}</ref>
== Previous mentions ==
| |||