Graham’s Schedules and the Number Partition Problem (NPP)

Graham’s Schedules and the Number Partition Problem (NPP) Seenu S. Reddi ReddiSS at aol dot com July 19, 2008 There is recent interest in the Number Partition Problem (NPP) (for instance see [1], [2]) and solutions are presented based on the Karp/Karmarkar technique for optimal partitions. We do not concern ourselves with this approach but rather solve the problem by pointing out the equivalence between the NPP and 2-Processor Scheduling (2PS), and using Graham’s schedules. Graham’s schedules are usually called Longest Processing Time (LPT) schedules in the literature but in view of his pioneering work in discovering these almost optimal schedules for the multi-processing problem and the fact that this discovery ranks next to the Selmer Johnson’s beautiful result about the two-machine flow-shop scheduling, we feel justified in our nomenclature. In the course of our solution, we present a priori bounds tighter than Graham’s and a posteriori bounds comparable to Coffman and Sethi [3]. We also derive asymptotic bounds when the numbers get large for specific conditions. We will state the two problems NPP and 2PS and establish the equivalence by a simple argument. Though this equivalence seems to be known and suspected by workers in the field, there was no simple and explicit proof offered (to the knowledge of the author). Assume a set of n numbers K = {t , t , …, t }which are positive and greater than zero. 1 2 nDefine S(K) = t + t + …, + t ...