{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T14:05:48Z","timestamp":1725631548790},"publisher-location":"Berlin, Heidelberg","reference-count":14,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642250101"},{"type":"electronic","value":"9783642250118"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011]]},"DOI":"10.1007\/978-3-642-25011-8_6","type":"book-chapter","created":{"date-parts":[[2011,11,8]],"date-time":"2011-11-08T20:27:34Z","timestamp":1320784054000},"page":"71-84","source":"Crossref","is-referenced-by-count":4,"title":["The 1-Neighbour Knapsack Problem"],"prefix":"10.1007","author":[{"given":"Glencora","family":"Borradaile","sequence":"first","affiliation":[]},{"given":"Brent","family":"Heeringa","sequence":"additional","affiliation":[]},{"given":"Gordon","family":"Wilfong","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"unstructured":"Boland, N., Fricke, C., Froyland, G., Sotirov, R.: Clique-based facets for the precedence constrained knapsack problem. Technical report. Tilburg University Repository, Netherlands (2005), \n \n http:\/\/arno.uvt.nl\/oai\/wo.uvt.nl.cgi","key":"6_CR1"},{"unstructured":"Borradaile, G., Heeringa, B., Wilfong, G.: The knapsack problem with neighbour constraints. CoRR, abs\/0910.0777 (2011)","key":"6_CR2"},{"issue":"4","key":"6_CR3","doi-asserted-by":"publisher","first-page":"634","DOI":"10.1145\/285055.285059","volume":"45","author":"U. Feige","year":"1998","unstructured":"Feige, U.: A threshold of ln n for approximating set cover. J. ACM\u00a045(4), 634\u2013652 (1998)","journal-title":"J. ACM"},{"unstructured":"Goundan, P.R., Schulz, A.S.: Revisiting the greedy approach to submodular set function maximization (2009) (preprint)","key":"6_CR4"},{"doi-asserted-by":"crossref","unstructured":"Halperin, E., Krauthgamer, R.: Polylogarithmic inapproximability. In: Proceedings of STOC, pp. 585\u2013594 (2003)","key":"6_CR5","DOI":"10.1145\/780542.780628"},{"key":"6_CR6","doi-asserted-by":"publisher","first-page":"463","DOI":"10.1145\/321906.321909","volume":"22","author":"O.H. Ibarra","year":"1975","unstructured":"Ibarra, O.H., Kim, C.E.: Fast approximation algorithms for the knapsack and sum of subset problems. J. ACM\u00a022, 463\u2013468 (1975)","journal-title":"J. ACM"},{"doi-asserted-by":"crossref","unstructured":"Johnson, D.S., Niemi, K.A.: On knapsacks, partitions, and a new dynamic programming technique for trees. Mathematics of Operations Research, 1\u201314 (1983)","key":"6_CR7","DOI":"10.1287\/moor.8.1.1"},{"key":"6_CR8","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-24777-7","volume-title":"Knapsack Problems","author":"H. Kellerer","year":"2004","unstructured":"Kellerer, H., Pferschy, U., Pisinger, D.: Knapsack Problems. Springer, Heidelberg (2004)"},{"issue":"1","key":"6_CR9","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1016\/S0020-0190(99)00031-9","volume":"70","author":"S. Khuller","year":"1999","unstructured":"Khuller, S., Moss, A., Naor(Seffi), J.: The budgeted maximum coverage problem. Inf. Process. Lett.\u00a070(1), 39\u201345 (1999)","journal-title":"Inf. Process. Lett."},{"issue":"8","key":"6_CR10","doi-asserted-by":"publisher","first-page":"889","DOI":"10.1016\/j.dam.2006.08.006","volume":"155","author":"S.G. Kolliopoulos","year":"2007","unstructured":"Kolliopoulos, S.G., Steiner, G.: Partially ordered knapsack and applications to scheduling. Discrete Applied Mathematics\u00a0155(8), 889\u2013897 (2007)","journal-title":"Discrete Applied Mathematics"},{"key":"6_CR11","doi-asserted-by":"publisher","first-page":"545","DOI":"10.1137\/1.9781611973068.60","volume-title":"Proceedings of the twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2009","author":"A. Kulik","year":"2009","unstructured":"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\u2013554. Society for Industrial and Applied Mathematics, Philadelphia (2009)"},{"key":"6_CR12","first-page":"323","volume-title":"Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009","author":"J. Lee","year":"2009","unstructured":"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\u2013332. ACM, New York (2009)"},{"issue":"1","key":"6_CR13","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1016\/S0167-6377(03)00062-2","volume":"32","author":"M. Sviridenko","year":"2004","unstructured":"Sviridenko, M.: A note on maximizing a submodular set function subject to a knapsack constraint. Operations Research Letters\u00a032(1), 41\u201343 (2004)","journal-title":"Operations Research Letters"},{"key":"6_CR14","volume-title":"Approximation Algorithms","author":"V. Vazirani","year":"2001","unstructured":"Vazirani, V.: Approximation Algorithms. Springer, Berlin (2001)"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Algorithms"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-25011-8_6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,16]],"date-time":"2019-04-16T01:29:37Z","timestamp":1555378177000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-25011-8_6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642250101","9783642250118"],"references-count":14,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-25011-8_6","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}