THE DIFFERENCING ALGORITHM LDM FOR PARTITIONING - A PROOF OF A CONJECTURE OF KARMARKAR AND KARP

Authors
YAKIR B
Citation
B. Yakir, THE DIFFERENCING ALGORITHM LDM FOR PARTITIONING - A PROOF OF A CONJECTURE OF KARMARKAR AND KARP, Mathematics of operations research, 21(1), 1996, pp. 85-99
Citations number
7
Categorie Soggetti
Operatione Research & Management Science",Mathematics,"Operatione Research & Management Science",Mathematics
Journal title
Mathematics of operations research → ACNP
ISSN journal
0364765X
Volume
21
Issue
1
Year of publication
1996
Pages
85 - 99
Database
ISI
SICI code
0364-765X(1996)21:1<85:TDALFP>2.0.ZU;2-3
Abstract
The algorithm LDM (largest differencing method) divides a list of n ra ndom items into two blocks. The parameter of interest is the expected difference between the two block sums. It is shown that if the items a re i.i.d. and uniform then the rate of convergence of this parameter t o zero is n(-Theta(log n)). An algorithm for balanced partitioning is constructed, with the same rate of convergence to zero.