Advanced Search
MyIDEAS: Login to save this paper or follow this series

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

Contents:

Author Info

  • Richard Engelbrecht-Wiggans
Registered author(s):

    Abstract

    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.

    Download Info

    If you experience problems downloading a file, check if you have the proper application to view it first. In case of further problems read the IDEAS help page. Note that these files are not on the IDEAS site. Please be patient as the files may be large.
    File URL: http://cowles.econ.yale.edu/P/cd/d04b/d0469.pdf
    Download Restriction: no

    Bibliographic Info

    Paper provided by Cowles Foundation for Research in Economics, Yale University in its series Cowles Foundation Discussion Papers with number 469.

    as in new window
    Length: 16 pages
    Date of creation: 1977
    Date of revision:
    Handle: RePEc:cwl:cwldpp:469

    Contact details of provider:
    Postal: Yale University, Box 208281, New Haven, CT 06520-8281 USA
    Phone: (203) 432-3702
    Fax: (203) 432-6167
    Web page: http://cowles.econ.yale.edu/
    More information through EDIRC

    Order Information:
    Postal: Cowles Foundation, Yale University, Box 208281, New Haven, CT 06520-8281 USA

    Related research

    Keywords:

    References

    No references listed on IDEAS
    You can help add them by filling out this form.

    Citations

    Lists

    This item is not listed on Wikipedia, on a reading list or among the top items on IDEAS.

    Statistics

    Access and download statistics

    Corrections

    When requesting a correction, please mention this item's handle: RePEc:cwl:cwldpp:469. See general information about how to correct material in RePEc.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Glena Ames).

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If references are entirely missing, you can add them using this form.

    If the full references list an item that is present in RePEc, but the system did not link to it, you can help with this form.

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your profile, as there may be some citations waiting for confirmation.

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.