Largest differencing method: Difference between revisions

Revision as of 00:41, 29 January 2023

Revision as of 19:32, 22 November 2023

Line 1:

In [[computer science]], the '''largest differencing method''' is an algorithm for solving the [[partition problem]] and the [[multiway number partitioning]]. It is also called the '''Karmarkar–Karp algorithm''' after its inventors, [[Narendra Karmarkar]] and [[Richard M. Karp]].<ref>[[Narendra Karmarkar]] and [[Richard M. Karp]], "The differencing method of set partitioning", Tech report UCB/CSD 82/113, Computer science division, [[University of California, Berkeley]], 1982</ref> It is often abbreviated as '''LDM.<ref name=":2">{{cite journal|last1=Michiels|first1=Wil|last2=Korst|first2=Jan|last3=Aarts|first3=Emile|year=2003|title=Performance ratios for the Karmarkar–Karp differencing method|journal=Electronic Notes in Discrete Mathematics|volume=13|pages=71–75|citeseerx=10.1.1.107.1332|doi=10.1016/S1571-0653(04)00442-1}}</ref>''' <ref name=":1">{{Cite journal
|last last1=Yakir
|first first1=Benjamin
| date=1996-02-01
| title=The Differencing Algorithm LDM for Partitioning: A Proof of a Conjecture of Karmarkar and Karp
|url=https://pubsonline.informs.org/doi/abs/10.1287/moor.21.1.85| journal=[[Mathematics of Operations Research]]
| volume=21
| issue=1
| pages=85–99
| doi=10.1287/moor.21.1.85|issn=0364-765X}}</ref>

| issn=0364-765X}}</ref>

== The algorithm ==