zbMATH — the first resource for mathematics

A note on maximizing a submodular set function subject to a knapsack constraint. (English) Zbl 1056.90124
Summary: We obtain an ($$1-\text e^{-1}$$)-approximation algorithm for maximizing a nondecreasing submodular set function subject to a knapsack constraint. This algorithm requires $$O(n^5)$$ function value computations.

MSC:
 90C27 Combinatorial optimization 90C59 Approximation methods and heuristics in mathematical programming
Full Text:
References:
 [1] Feige, U., A threshold of $$lnn$$ for approximating set cover, J. ACM, 45, 634-652, (1998) · Zbl 1065.68573 [2] A. Hoffman, J. Lee, J. Williams, New upper bounds for maximum-entropy sampling, mODa 6—advances in model-oriented design and analysis (Puchberg/Schneeberg, 2001) Contributory Statististics, Physica, Heidelberg, 2001, pp. 143-153. [3] Khuller, S.; Moss, A.; Naor, J., The budgeted maximum coverage problem, Inform. process. lett., 70, 39-45, (1999) · Zbl 1002.68203 [4] Ko, Chun-Wa; Lee, J.; Queyranne, M., An exact algorithm for maximum entropy sampling, Oper. res., 43, 684-691, (1995) · Zbl 0857.90069 [5] Lee, J., Constrained maximum-entropy sampling, Oper. res., 46, 655-664, (1998) · Zbl 1009.62599 [6] Nemhauser, G.L.; Wolsey, L.A.; Fisher, M.L., An analysis of approximations for maximizing submodular set functions-1, Math. programming, 14, 265-294, (1978) · Zbl 0374.90045 [7] Sahni, S., Approximate algorithms for the 0/1 knapsack problem, J. ACM, 22, 115-124, (1975) · Zbl 0362.90066 [8] Wolsey, L.A., Maximising real-valued submodular functionsprimal and dual heuristics for location problems, Math. oper. res., 7, 410-425, (1982) · Zbl 0498.90024
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.