Abstract
Let N be a finite set and
a nonempty collection of subsets of N which have the property that
and F 2⊂F 1 imply
. A real-valued function z defined on the subsets of N that satifies z(S)≤z(T) for all S⊂T⊃-N and z(S)+z(T)≥(S∪T)+z(S∩T) for all S,T⊂-N is called nondecreasing and submodular. We consider the problem
, z(S) submodular and nondecreasing} and several special cases of it.
We analyze greedy and local improvement heuristics, and a linera programming relaxation when z(S) is linear. Our results are worst case bounds on the quality of the approximations. For example, when (N,
) is described by the intersection of P matroids, we show that a greedy heuristic always produces a solution whose value is at least 1/(P+1) times the optimal value. This bound can be achieved for all positive integers P.
Supported, in part, by NSF Grant ENG 76-20274.
Cornell University and supported, in part, by NSF Grant ENG 75-00568.
Preview
Unable to display preview. Download preview PDF.
References
A.K. Chandra and C.K. Wong, “Worst case analysis of a placement algorithm related to storage allocation”, SIAM Journal on Computing 4 (1975) 249–263.
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, 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.
T.A. Jenkyns, “The efficiency of the “greedy” algorithm”, in: Proceedings of the 7th S.E. Conference on combinatorics, graph theory and computing (Utilitas Mathematica, Winnipeg, 1976) pp. 341–350.
B. Korte and D. Hausmann, “An analysis of the greedy heuristic for independence systems”, Report No 7645, Institut für ökonometrie und Operations Research, Universität Bonn, May 1976.
G.L. Nemhauser, L.A. Wolsey and M.L. Fisher, “An analysis of approximations for maximizing submodular set functions—I”, Discussion Paper No 7618, Center for Operations Research and Econometrics, University of Louvain, July 1976, Mathematical Programming to appear.
S. Sahni and T. Gonzalez, “P-complete approximation problems”, Journal of the Association for Computing Machinery 23 (1976) 555–565.
R. von Randow. Introduction to the theory of matroids, (Springer, Berlin, 1975).
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1978 The Mathematical Programming Society
About this chapter
Cite this chapter
Fisher, M.L., Nemhauser, G.L., Wolsey, L.A. (1978). An analysis of approximations for maximizing submodular set functions—II. In: Balinski, M.L., Hoffman, A.J. (eds) Polyhedral Combinatorics. Mathematical Programming Studies, vol 8. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0121195
Download citation
DOI: https://doi.org/10.1007/BFb0121195
Received:
Revised:
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-00789-7
Online ISBN: 978-3-642-00790-3
eBook Packages: Springer Book Archive