An analysis of approximations for maximizing submodular set functions-I. (English) Zbl 0374.90045


90C05 Linear programming
05C35 Extremal problems in graph theory
Full Text: DOI


[1] D.A. Babayev, ”Comments on the note of Frieze”,Mathematical Programming 7 (1974) 249–252. · Zbl 0294.90056
[2] 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. · Zbl 0361.90034
[3] 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. · Zbl 0197.00802
[4] 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.
[5] J. Edmonds, ”Matroids and the greedy algorithm”,Mathematical Programming 1 (1971) 127–136. · Zbl 0253.90027
[6] A.M. Frieze, ”A cost function property for plant location problems”,Mathematical Programming 7 (1974) 245–248. · Zbl 0292.90039
[7] L.S. Shapley, ”Complements and substitutes in the optimal assignment problem”,Naval Research Logistics Quarterly 9 (1962) 45–48.
[8] L.S. Shapley, ”Cores of convex games”,International Journal of Game Theory 1 (1971) 11–26. · Zbl 0222.90054
[9] K. Spielberg, ”Plant location with generalized search origin”,Management Science 16 (1969) 165–178.
[10] D.R. Woodall, ”Application of polymatroids and linear programming to transversals and graphs”, presented at the 1973 British Combinatorial Conference (Aberystwyth). · Zbl 0295.05008
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.