A performance guarantee for the greedy set-partitioning algorithm (Q790814): Difference between revisions

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 set to the smallest set is as small as possible. Let \(\rho_ g(S)\) be the value of this ratio using the greedy or largest-first rule and \(\rho_ 0(S)\) be the smallest possible value of this ratio, i.e., the optimal value. The authors prove that \(\rho_ g(S)/\rho_ 0(S)\leq 7/5,\) and that this is a best possible bound for all m.