An analysis of approximations for maximizing submodular set functions II
(1978) Mathematical Programming Studies — Vol. 8, p. 73-87 (1978)
Files
No attached file found for this publication.
Details
- Authors
- 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)gez(SxcupT)+z(SxcapT) for allS, T inN. Such a function is called submodular. We consider the problem maxSsubN{a(S):|S|leK,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 ldquogreedyrdquo 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.
- Affiliations
Citations
Fisher, M. L., Nemhauser, G. L., & Wolsey, L. (1978). An analysis of approximations for maximizing submodular set functions II. Mathematical Programming Studies, 8, 73-87. https://doi.org/10.1007/BFb0121195 (Original work published 1978)