Partitioning ideal sets

Abstract

This paper analyzes a class of approximation algorithms for the NP-complete problem [4] of partitioning a given set of positive real numbers into k subsets. Chandra and Wong [2] analyzed one such algorithm (Graham's LPT rule) for the L ₂ metric on the related classic scheduling problem and proved a 25/24 worst case upper bound in the general case. This result was slightly improved by Leung and Wei [9]. The input sets considered in this paper are sets which have a k-partition with equal sum subsets (termed ideal sets); we prove a new tight upper bound of 37/ 36 for the L ₂ norm on such sets for the entire class of algorithms.

Keywords:

• Mathematical programming
• NP-complete
• scheduling theory
• worst-case analysis

^*Corresponding author.

^*Corresponding author.

Notes

^*Corresponding author.