{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T10:56:28Z","timestamp":1743072988528,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642208065"},{"type":"electronic","value":"9783642208072"}],"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"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011]]},"DOI":"10.1007\/978-3-642-20807-2_14","type":"book-chapter","created":{"date-parts":[[2011,6,18]],"date-time":"2011-06-18T09:58:49Z","timestamp":1308391129000},"page":"170-182","source":"Crossref","is-referenced-by-count":1,"title":["Set Covering with Ordered Replacement: Additive and Multiplicative Gaps"],"prefix":"10.1007","author":[{"given":"Friedrich","family":"Eisenbrand","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Naonori","family":"Kakimura","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Thomas","family":"Rothvo\u00df","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Laura","family":"Sanit\u00e0","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"14_CR1","doi-asserted-by":"publisher","first-page":"58","DOI":"10.1002\/nav.10058","volume":"50","author":"A. Caprara","year":"2003","unstructured":"Caprara, A., Kellerer, H., Pferschy, U.: Approximation schemes for ordered vector packing problems. Naval Research Logistics\u00a050, 58\u201369 (2003)","journal-title":"Naval Research Logistics"},{"issue":"3","key":"14_CR2","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1287\/moor.4.3.233","volume":"4","author":"V. Chv\u00e1tal","year":"1979","unstructured":"Chv\u00e1tal, V.: A greedy heuristic for the set-covering problem. Mathematics of Operations Research\u00a04(3), 233\u2013235 (1979)","journal-title":"Mathematics of Operations Research"},{"key":"14_CR3","doi-asserted-by":"crossref","unstructured":"Das, A., Mathieu, C., Mozes, S.: The train delivery problem- vehicle routing meets bin packing (2010)","DOI":"10.1007\/978-3-642-18318-8_9"},{"key":"14_CR4","volume-title":"Symposium on Discrete Algorithms, SODA 2011","author":"F. Eisenbrand","year":"2011","unstructured":"Eisenbrand, F., P\u00e1lv\u00f6lgyi, D., Rothvo\u00df, T.: Bin packing via discrepancy of permutations. In: Symposium on Discrete Algorithms, SODA 2011. SIAM, Philadelphia (2011)"},{"key":"14_CR5","doi-asserted-by":"crossref","unstructured":"Epstein, L., Levin, A.: An APTAS for generalized cost variable-sized bin packing. SIAM Journal on Computing, 38(1) (2008)","DOI":"10.1137\/060670328"},{"issue":"1","key":"14_CR6","doi-asserted-by":"publisher","first-page":"32","DOI":"10.1016\/j.ipl.2008.08.005","volume":"109","author":"L. Epstein","year":"2008","unstructured":"Epstein, L., Levin, A.: Asymptotic fully polynomial approximation schemes for variants of open-end bin packing. Inf. Process. Lett.\u00a0109(1), 32\u201337 (2008)","journal-title":"Inf. Process. Lett."},{"key":"14_CR7","doi-asserted-by":"crossref","unstructured":"Epstein, L., Levin, A.: AFPTAS results for common variants of bin packing: A new method to handle the small items. SIAM Journal on Optimization (2010) (to appear)","DOI":"10.1137\/090767613"},{"key":"14_CR8","doi-asserted-by":"crossref","unstructured":"Epstein, L., Levin, A.: Bin packing with general cost structures. Mathematical Programming (2010) (to appear)","DOI":"10.1007\/s10107-010-0403-5"},{"issue":"4","key":"14_CR9","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. Journal of the ACM\u00a045(4), 634\u2013652 (1998)","journal-title":"Journal of the ACM"},{"issue":"4","key":"14_CR10","doi-asserted-by":"publisher","first-page":"349","DOI":"10.1007\/BF02579456","volume":"1","author":"W. Fernandez de la Vega","year":"1981","unstructured":"Fernandez de la Vega, W., Lueker, G.S.: Bin packing can be solved within 1\u2009+\u2009\u03b5 in linear time. Combinatorica\u00a01(4), 349\u2013355 (1981)","journal-title":"Combinatorica"},{"key":"14_CR11","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company, New York (1979)"},{"issue":"2","key":"14_CR12","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1006\/jctb.1996.0067","volume":"68","author":"J. Kahn","year":"1996","unstructured":"Kahn, J.: Asymptotics of the chromatic index for multigraphs. Journal of Combinatorial Theory. Series B\u00a068(2), 233\u2013254 (1996)","journal-title":"Journal of Combinatorial Theory. Series B"},{"key":"14_CR13","doi-asserted-by":"publisher","first-page":"312","DOI":"10.1109\/SFCS.1982.61","volume-title":"23rd annual symposium on foundations of computer science (Chicago, Ill., 1982)","author":"N. Karmarkar","year":"1982","unstructured":"Karmarkar, N., Karp, R.M.: An efficient approximation scheme for the one-dimensional bin-packing problem. In: 23rd annual symposium on foundations of computer science (Chicago, Ill., 1982), pp. 312\u2013320. IEEE, New York (1982)"},{"issue":"4","key":"14_CR14","doi-asserted-by":"publisher","first-page":"383","DOI":"10.1016\/0012-365X(75)90058-8","volume":"13","author":"L. Lov\u00e1sz","year":"1975","unstructured":"Lov\u00e1sz, L.: On the ratio of optimal integral and fractional covers. Discrete Mathematics\u00a013(4), 383\u2013390 (1975)","journal-title":"Discrete Mathematics"},{"key":"14_CR15","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511813603","volume-title":"Probability and computing","author":"M. Mitzenmacher","year":"2005","unstructured":"Mitzenmacher, M., Upfal, E.: Probability and computing. Cambridge University Press, Cambridge (2005); Randomized algorithms and probabilistic analysis"},{"issue":"1-3","key":"14_CR16","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1016\/S0012-365X(98)00356-2","volume":"202","author":"M. Plantholt","year":"1999","unstructured":"Plantholt, M.: A sublinear bound on the chromatic index of multigraphs. Discrete Mathematics\u00a0202(1-3), 201\u2013213 (1999)","journal-title":"Discrete Mathematics"},{"key":"14_CR17","unstructured":"Rothvo\u00df, T.: The entropy rounding method in approximation algorithms (2010) (submitted)"},{"key":"14_CR18","volume-title":"Approximation Algorithms","author":"V.V. Vazirani","year":"2001","unstructured":"Vazirani, V.V.: Approximation Algorithms. Springer, Heidelberg (2001)"},{"issue":"6","key":"14_CR19","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1016\/S0020-0190(97)00179-8","volume":"64","author":"G.J. Woeginger","year":"1997","unstructured":"Woeginger, G.J.: There is no asymptotic PTAS for two-dimensional vector packing. Information Processing Letters\u00a064(6), 293\u2013297 (1997)","journal-title":"Information Processing Letters"}],"container-title":["Lecture Notes in Computer Science","Integer Programming and Combinatoral Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-20807-2_14","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,19]],"date-time":"2019-05-19T20:13:49Z","timestamp":1558296829000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-20807-2_14"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642208065","9783642208072"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-20807-2_14","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}