Thumbnail
Access Restriction
Open

Author Korf, Richard E.
Source CiteSeerX
Content type Text
File Format PDF
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Abstract Given a set of numbers, the two-way partitioning problem is to divide them into two subsets, so that the sum of the numbers in each subset are as nearly equal as possible. The problem is NPcomplete, and is contained in many scheduling applications. Based on a polynomial-time heuristic due to Karmarkar and Karp, we present a new algorithm, called Complete Karmarkar Karp (CKK), that optimally solves the general number-partitioning problem, and significantly outperforms the best previously-known algorithms for this problem. By restricting the numbers to twelve significant digits, CKK can optimally solve two-way partitioning problems of arbitrary size in practice. Arbitrary-size three-way partitioning problems with up to six digits of precision are solvable. For numbers with greater precision, CKK first returns the Karmarkar-Karp solution, then continues to find better solutions as time allows. Over six orders of magnitude improvement in solution quality is obtained in less than an hour of...
Educational Role Student ♦ Teacher
Age Range above 22 year
Educational Use Research
Education Level UG and PG ♦ Career/Technical Study
Publisher Date 1995-01-01