Partitioning under the Lp norm

This paper analyzes the NP-complete problem (M.R. Garey, D.S. Johnson, Computers and Intractability, Freeman, New York, 1979) of finding an optimal partition of k subsets for a given set of positive real numbers. A number of norms (L-2 L-infinity and more generally, L-p) have been utilized to measure the competitive ratio of the partition obtained. Chandra and Wong (A.K. Chandra, C.K. Wong, Worst-case analysis of a placement algorithm related to storage allocation, SIAM Journal on Computing 4 (3) (1975) 249-264) analyzed Graham's LPT rule for the L-p norm and proved a 3/2 worst case upper bound in the general case. A class of algorithms to solve this partitioning problem is introduced that relaxes Graham's LPT rule (R.L. Graham, Bounds on multiprocessing timing anomalies, SIAM Journal of Applied Mathematics 17 (1969) 263-269) so that the current element can be placed in (almost) any subset instead of just the minimal subset. The input sets considered in this paper are sets which can yield a k-partition with equal sum subsets (termed ideal sets). Specifically, it is shown that for the L-p norm, any algorithm of the class has an upper bound of 4/3 for the competitive ratio on ideal sets. It is also shown that this is the best possible such upper bound. (C) 2000 Elsevier Science B.V. All rights reserved.