Abstract
LetN be a finite set andz be a real-valued function defined on the set of subsets ofN that satisfies z(S)+z(T)≥z(S⋃T)+z(S⋂T) for allS, T inN. Such a function is called submodular. We consider the problem maxS⊂N{a(S):|S|≤K,z(S) submodular}.
Several hard combinatorial optimization problems can be posed in this framework. For example, the problem of finding a maximum weight independent set in a matroid, when the elements of the matroid are colored and the elements of the independent set can have no more thanK colors, is in this class. The uncapacitated location problem is a special case of this matroid optimization problem.
We analyze greedy and local improvement heuristics and a linear programming relaxation for this problem. Our results are worst case bounds on the quality of the approximations. For example, whenz(S) is nondecreasing andz(0) = 0, we show that a “greedy” heuristic always produces a solution whose value is at least 1 −[(K − 1)/K] K times the optimal value. This bound can be achieved for eachK and has a limiting value of (e − 1)/e, where e is the base of the natural logarithm.
Similar content being viewed by others
References
D.A. Babayev, “Comments on the note of Frieze”,Mathematical Programming 7 (1974) 249–252.
G. Cornuejols, M.L. Fisher and G.L. Nemhauser, “Location of bank accounts to optimize float: An analytic study of exact and approximate algorithms”,Management Science 23 (1977) 789–810.
J. Edmonds, “Matroid partition”, in: G.B. Dantzig and A.M. Veinott, eds.,Mathematics of the decision sciences, A.M.S. Lectures in Applied Mathematics 11 (Am. Math. Soc., Providence, RI, 1968) pp. 333–345.
J. Edmonds, “Submodular functions, matroids and certain polyhedra”, in: R. Guy, ed.,Combinatorial structures and their applications (Gordon and Breach, New York, 1971) pp. 69–87.
J. Edmonds, “Matroids and the greedy algorithm”,Mathematical Programming 1 (1971) 127–136.
A.M. Frieze, “A cost function property for plant location problems”,Mathematical Programming 7 (1974) 245–248.
L.S. Shapley, “Complements and substitutes in the optimal assignment problem”,Naval Research Logistics Quarterly 9 (1962) 45–48.
L.S. Shapley, “Cores of convex games”,International Journal of Game Theory 1 (1971) 11–26.
K. Spielberg, “Plant location with generalized search origin”,Management Science 16 (1969) 165–178.
D.R. Woodall, “Application of polymatroids and linear programming to transversals and graphs”, presented at the 1973 British Combinatorial Conference (Aberystwyth).
Author information
Authors and Affiliations
Additional information
On leave of absence from Cornell University and supported, in part, by NSF Grant ENG 75-00568.
Supported, in part, by NSF Grant ENG 76-20274.
Rights and permissions
About this article
Cite this article
Nemhauser, G.L., Wolsey, L.A. & Fisher, M.L. An analysis of approximations for maximizing submodular set functions—I. Mathematical Programming 14, 265–294 (1978). https://doi.org/10.1007/BF01588971
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01588971