This paper analyzes an approximation algorithm (Graham's LPT rule) for the NP-complete problem of partitioning a given set of positive real numbers into k subsets. Chandra and Wong analyzed the same algorithm for the L2 metric for the similar classic scheduling problem and proved a 25/24 worst-case upper bound. This result was slightly improved by Leung and Wei. This paper considers this algorithm on sets which have a k-partition with equal sum subsets and proves a new tight upper bound of 37/36 for the L2 norm on such sets. To achieve this result we apply the statistical notion of variance to the partition obtained by the approximation algorithm. By Lagrange multiplier analysis, the maximum variance is shown not to exceed wk+3/2 where wk+3 is the k + 3rd largest number in the set S. Sets of numbers are provided such that the tight bounds are achieved by the algorithm applied to this set.
