Let S be a set of positive numbers and m an integer not less than 2. The problem is to partition S into m subsets such that the ratio of the largest subset sum to the smallest is as small as possible. Let &rgr;g(S) be the value of this ratio using the greedy or largest-first rule and &rgr;0(S) be the smallest possible value of this ratio, i.e., the optimal value. The authors prove that :9I and that this is a best possible bound for all m.
--Authors’ Summary
The authors present these proofs and briefly remark on the greedy rule’s behavior in more restricted settings. Application contexts for the problem are unfortunately not discussed.
