The differencing algorithm largest differencing method for partitioning: a proof of a conjecture of Karmarkar and Karp

The differencing algorithm largest differencing method for partitioning: a proof of a conjecture of Karmarkar and Karp

0.00 Avg rating0 Votes
Article ID: iaor20041883
Country: United States
Volume: 21
Issue: 1
Start Page Number: 85
End Page Number: 99
Publication Date: Feb 1996
Journal: Mathematics of Operations Research
Authors:
Abstract:

The algorithm LDM (largest differencing method) divides a list of n random items into two blocks. The parameter of interest is the expected difference between the two block sums. It is shown that if the items are independent, identically distributed and uniform then the rate of convergence of this parameter to zero is n–Θ(log(n)). An algorithm for balanced partitioning is constructed, with the same rate of convergence to zero.

Reviews

Required fields are marked *. Your email address will not be published.