The Greedy Heuristic Applied to a Class of Set Partitioning and Subset Selection Problems

The greedy heuristic may be used to obtain approximate solutions to integer programming problems. For some classes of problems, notably knapsack problems related to the coin changing problem, the greedy heuristic results in optimal solutions. However, the greedy heuristic does quite poorly at maximizing submodular set functions.

This paper considers a class of set partitioning and subset selection problems. Results similar to those for maximizing submodular set functions are obtained for less restricted objective functions. The example used to show how poorly the heuristic does is motivated by a problem arising from an actual auction; the negative results are not mere mathematical pathologies but genuine shortcomings of the greedy heuristic.

The greedy heuristic is quite successful at solving a class of knapsack problems related to the coin changing problem. Chang and Korsh [2], Hu and Lenard [5], Johnson and Kernighan [7], and Magazine, Nemhauser, and Trotter [8] show that the greedy heuristic results in optimal solutions for such problems. Problems of optimal subset selection have been studied by Boyce, Farhi, and Weischedel [1], indicating the need for a simply heuristic for obtaining approximate solutions. Fisher, Nemhauser, and Wolsey [4, 9, 10] have shown that the greedy heuristic may result in a solution for problems of maximizing submodular set functions with a value which is a relatively small fraction of the optimum.

This paper derives similar results for a wider class of set partitioning and subset selection problems. The problem is formulated in the first section of the paper. Although the motivating problem results in a set partitioning problem, the results of the later sections apply as well to a wider class of subset selection problems. The more general problem statement is given as problem II; however, most of the discussion uses examples from the more restrictive problem I.

The second section considers various possible restrictions to be placed on the objective function. The conditions may be stated in terms of either of the problem statements; the two forms of the conditions are shown to be essentially equivalent. Included among the possibilities are submodular set functions and several alternatives which are relaxations of submodularity. The relative generality of the various possibilities is illustrated by a couple of simple examples.

The next two sections contain the main results of the paper. Objective functions which are “normal,” “monotonic,” and “discounted” are considered first. For such cases, the greedy heuristic solution is shown to have a value of at least 1/m of the optimal value, where m is the cardinality of the largest feasible subsets. The third section concludes by presenting a class of examples for which the greedy solution value is arbitrarily little more than the bound established above.

Similar bounds may be obtained if the “discounted” condition is replaced by “variably discountedness,” although now the bounds must be functions of the variable discounting functions. Again, a lower bound is derived for the greedy solution value. The section concludes by presenting a class of examples for which the greedy solution value is arbitrarily little more than this bound.

The last section is an attempt to reassure the reader that the above results are not simply pathological cases. An actual real estate auction [6] is briefly described. This real world problem is used to motivate bidding functions (of two hypothetical bidders) similar to those used to establish the tightness of the bound in sections three and four. This discussion suggests that the results are not mere mathematical pathologies and that, from many a practical viewpoint, the greed heuristic is not a satisfactory algorithm for obtaining optimal solutions to set partitioning and subset selection problems.