An analysis of approximations for maximizing submodular set functions. I
(1978) Mathematical Programming — Vol. 14, n° 3, p. 265-294 (1978)
Files
No attached file found for this publication.
Details
- Authors
- Abstract
- Let /b N/ be a finite set and /b z/ be a real-valued function defined on the set of subsets of /b N/ that satisfies /b z /(/b S/)+/b z/(/b T/)>or=/b z/(/b S/ U /b T/)+ /b z/(/b S/ intersect /b T/) for all /b S/, /b T/ in /b N/. Such a function is called submodular. The author considers the problem max/sub S sube N/{/b z/(/b S/):|/b S/|<or=/b K/, /b z /(/b 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 than /b K/ colors, is in this class. The uncapacitated location problem is a special case of this matroid optimization problem. The author analyzes greedy and local improvement heuristics and a linear programming relaxation for this problem.
- Affiliations
Citations
Nemhauser, G. L., Wolsey, L., & Fisher, M. L. (1978). An analysis of approximations for maximizing submodular set functions. I. Mathematical Programming, 14(3), 265-294. https://hdl.handle.net/2078.5/70311 (Original work published 1978)