1. Boland, N., Fricke, C., Froyland, G., Sotirov, R.: Clique-based facets for the precedence constrained knapsack problem. Technical report. Tilburg University Repository, Netherlands (2005),http://arno.uvt.nl/oai/wo.uvt.nl.cgi

2. Borradaile, G., Heeringa, B., Wilfong, G.: The knapsack problem with neighbour constraints. CoRR, abs/0910.0777 (2011)

   Google Scholar 

3. Feige, U.: A threshold of lnn for approximating set cover. J. ACM 45(4), 634–652 (1998)

   Article MathSciNet MATH  Google Scholar 

4. Goundan, P.R., Schulz, A.S.: Revisiting the greedy approach to submodular set function maximization (2009) (preprint)

   Google Scholar 

5. Halperin, E., Krauthgamer, R.: Polylogarithmic inapproximability. In: Proceedings of STOC, pp. 585–594 (2003)

   Google Scholar 

6. Ibarra, O.H., Kim, C.E.: Fast approximation algorithms for the knapsack and sum of subset problems. J. ACM 22, 463–468 (1975)

   Article MathSciNet MATH  Google Scholar 

7. Johnson, D.S., Niemi, K.A.: On knapsacks, partitions, and a new dynamic programming technique for trees. Mathematics of Operations Research, 1–14 (1983)

   Google Scholar 

8. Kellerer, H., Pferschy, U., Pisinger, D.: Knapsack Problems. Springer, Heidelberg (2004)

   Book MATH  Google Scholar 

9. Khuller, S., Moss, A., Naor(Seffi), J.: The budgeted maximum coverage problem. Inf. Process. Lett. 70(1), 39–45 (1999)

   Article MathSciNet MATH  Google Scholar 

10. Kolliopoulos, S.G., Steiner, G.: Partially ordered knapsack and applications to scheduling. Discrete Applied Mathematics 155(8), 889–897 (2007)

    Article MathSciNet MATH  Google Scholar 

11. Kulik, A., Shachnai, H., Tamir, T.: Maximizing submodular set functions subject to multiple linear constraints. In: Proceedings of the twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2009, pp. 545–554. Society for Industrial and Applied Mathematics, Philadelphia (2009)

    Chapter  Google Scholar 

12. Lee, J., Mirrokni, V.S., Nagarajan, V., Sviridenko, M.: Non-monotone submodular maximization under matroid and knapsack constraints. In: Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009, pp. 323–332. ACM, New York (2009)

    Google Scholar 

13. Sviridenko, M.: A note on maximizing a submodular set function subject to a knapsack constraint. Operations Research Letters 32(1), 41–43 (2004)

    Article MathSciNet MATH  Google Scholar 

14. Vazirani, V.: Approximation Algorithms. Springer, Berlin (2001)

    MATH  Google Scholar 

Download references