{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,7]],"date-time":"2024-09-07T21:41:12Z","timestamp":1725745272322},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642403279"},{"type":"electronic","value":"9783642403286"}],"license":[{"start":{"date-parts":[[2013,1,1]],"date-time":"2013-01-01T00:00:00Z","timestamp":1356998400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-40328-6_12","type":"book-chapter","created":{"date-parts":[[2013,8,16]],"date-time":"2013-08-16T09:17:34Z","timestamp":1376644654000},"page":"158-172","source":"Crossref","is-referenced-by-count":1,"title":["Shrinking Maxima, Decreasing Costs: New Online Packing and Covering Problems"],"prefix":"10.1007","author":[{"given":"Pierre","family":"Fraigniaud","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Magn\u00fas M.","family":"Halld\u00f3rsson","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Boaz","family":"Patt-Shamir","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dror","family":"Rawitz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Adi","family":"Ros\u00e9n","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"2","key":"12_CR1","doi-asserted-by":"publisher","first-page":"361","DOI":"10.1137\/060661946","volume":"39","author":"N. Alon","year":"2009","unstructured":"Alon, N., Awerbuch, B., Azar, Y., Buchbinder, N., Naor, J.: The online set cover problem. SIAM Journal on Computing\u00a039(2), 361\u2013370 (2009)","journal-title":"SIAM Journal on Computing"},{"key":"12_CR2","unstructured":"Awerbuch, B., Azar, Y., Plotkin, S.A.: Throughput-competitive on-line routing. In: Proc. 34th FOCS, pp. 32\u201340 (1993)"},{"key":"12_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1007\/978-3-642-15369-3_4","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"M. Bateni","year":"2010","unstructured":"Bateni, M., Hajiaghayi, M., Zadimoghaddam, M.: Submodular secretary problem and extensions. In: Serna, M., Shaltiel, R., Jansen, K., Rolim, J. (eds.) APPROX and RANDOM 2010. LNCS, vol.\u00a06302, pp. 39\u201352. Springer, Heidelberg (2010)"},{"issue":"3","key":"12_CR4","first-page":"178","volume":"7","author":"P. Berman","year":"2000","unstructured":"Berman, P.: A d\/2 approximation for maximum weight independent set in d-claw free graphs. Nord. J. Comput.\u00a07(3), 178\u2013184 (2000)","journal-title":"Nord. J. Comput."},{"issue":"2","key":"12_CR5","doi-asserted-by":"publisher","first-page":"270","DOI":"10.1287\/moor.1080.0363","volume":"34","author":"N. Buchbinder","year":"2009","unstructured":"Buchbinder, N., Naor, J.: Online primal-dual algorithms for covering and packing. Math. Oper. Res.\u00a034(2), 270\u2013286 (2009)","journal-title":"Math. Oper. Res."},{"issue":"4","key":"12_CR6","doi-asserted-by":"publisher","first-page":"837","DOI":"10.1137\/S0097539799356265","volume":"33","author":"C. Chekuri","year":"2004","unstructured":"Chekuri, C., Khanna, S.: On multidimensional packing problems. SIAM Journal on Computing\u00a033(4), 837\u2013851 (2004)","journal-title":"SIAM Journal on Computing"},{"key":"12_CR7","doi-asserted-by":"crossref","unstructured":"Cygan, M.: Improved approximation for 3-dimensional matching via bounded pathwidth local search. arXiv report 1304.1424 (April 2013)","DOI":"10.1109\/FOCS.2013.61"},{"issue":"4","key":"12_CR8","doi-asserted-by":"publisher","first-page":"728","DOI":"10.1137\/110820774","volume":"41","author":"Y. Emek","year":"2012","unstructured":"Emek, Y., Halld\u00f3rsson, M.M., Mansour, Y., Patt-Shamir, B., Radhakrishnan, J., Rawitz, D.: Online set packing. SIAM Journal on Computing\u00a041(4), 728\u2013746 (2012)","journal-title":"SIAM Journal on Computing"},{"key":"12_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"218","DOI":"10.1007\/978-3-642-22935-0_19","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"M. Feldman","year":"2011","unstructured":"Feldman, M., Naor, J(S.), Schwartz, R.: Improved competitive ratios for submodular secretary problems (Extended abstract). In: Goldberg, L.A., Jansen, K., Ravi, R., Rolim, J.D.P. (eds.) APPROX\/RANDOM 2011. LNCS, vol.\u00a06845, pp. 218\u2013229. Springer, Heidelberg (2011)"},{"issue":"2","key":"12_CR10","doi-asserted-by":"publisher","first-page":"189","DOI":"10.2307\/1402748","volume":"51","author":"P. Freeman","year":"1983","unstructured":"Freeman, P.: The secretary problem and its extensions: a review. Internat. Statist. Rev.\u00a051(2), 189\u2013206 (1983)","journal-title":"Internat. Statist. Rev."},{"key":"12_CR11","doi-asserted-by":"publisher","first-page":"100","DOI":"10.1016\/0377-2217(84)90053-5","volume":"15","author":"A.M. Frieze","year":"1984","unstructured":"Frieze, A.M., Clarke, M.R.B.: Approximation algorithms for the m-dimensional 0\u2009\u2212\u20091 knapsack problem: worst-case and probabilistic analyses. Eur. J. Oper. Res.\u00a015, 100\u2013109 (1984)","journal-title":"Eur. J. Oper. Res."},{"key":"12_CR12","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1080\/01621459.1966.10502008","volume":"61","author":"J.P. Gilbert","year":"1966","unstructured":"Gilbert, J.P., Mosteller, F.: Recognizing the maximum of a sequence. J. Amer. Statist. Assoc.\u00a061, 35\u201373 (1966)","journal-title":"J. Amer. Statist. Assoc."},{"issue":"1-3","key":"12_CR13","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1016\/S0166-218X(99)00124-9","volume":"99","author":"M.M. Halld\u00f3rsson","year":"2000","unstructured":"Halld\u00f3rsson, M.M., Kratochv\u00edl, J., Telle, J.A.: Independent sets with domination constraints. Discrete Applied Mathematics\u00a099(1-3), 39\u201354 (2000)","journal-title":"Discrete Applied Mathematics"},{"issue":"1","key":"12_CR14","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1007\/BF02392825","volume":"182","author":"J. H\u00e5stad","year":"1999","unstructured":"H\u00e5stad, J.: Clique is hard to approximate within n\n                  1\u2009\u2212\u2009\u03b5\n                  . Acta Mathematica\u00a0182(1), 105\u2013142 (1999)","journal-title":"Acta Mathematica"},{"issue":"1","key":"12_CR15","doi-asserted-by":"publisher","first-page":"20","DOI":"10.1007\/s00037-006-0205-6","volume":"15","author":"E. Hazan","year":"2006","unstructured":"Hazan, E., Safra, S., Schwartz, O.: On the complexity of approximating k-set packing. Computational Complexity\u00a015(1), 20\u201339 (2006)","journal-title":"Computational Complexity"},{"issue":"4","key":"12_CR16","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. Journal of the ACM\u00a022(4), 463\u2013468 (1975)","journal-title":"Journal of the ACM"},{"issue":"2","key":"12_CR17","doi-asserted-by":"publisher","first-page":"244","DOI":"10.1287\/moor.9.2.244","volume":"9","author":"M.J. Magazine","year":"1984","unstructured":"Magazine, M.J., Chern, M.-S.: A note on approximation schemes for multidimensional knapsack problems. Math. Oper. Res.\u00a09(2), 244\u2013247 (1984)","journal-title":"Math. Oper. Res."},{"key":"12_CR18","doi-asserted-by":"crossref","unstructured":"Mansour, Y., Patt-Shamir, B., Rawitz, D.: Overflow management with multipart packets. In: IEEE INFOCOM (2011)","DOI":"10.1109\/INFCOM.2011.5935087"},{"issue":"4","key":"12_CR19","doi-asserted-by":"publisher","first-page":"365","DOI":"10.1007\/BF02579324","volume":"7","author":"P. Raghavan","year":"1987","unstructured":"Raghavan, P., Thompson, C.D.: Randomized rounding: a technique for provably good algorithms and algorithmic proofs. Combinatorica\u00a07(4), 365\u2013374 (1987)","journal-title":"Combinatorica"},{"issue":"1","key":"12_CR20","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1145\/321864.321873","volume":"22","author":"S. Sahni","year":"1975","unstructured":"Sahni, S.: Approximate algorithms for the 0\/1 knapsack problem. Journal of the ACM\u00a022(1), 115\u2013124 (1975)","journal-title":"Journal of the ACM"},{"key":"12_CR21","doi-asserted-by":"crossref","unstructured":"Srinivasan, A.: Improved approximations of packing and covering problems. In: 27th Annual ACM Symposium on the Theory of Computing, pp. 268\u2013276 (1995)","DOI":"10.1145\/225058.225138"}],"container-title":["Lecture Notes in Computer Science","Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-40328-6_12","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,19]],"date-time":"2019-05-19T21:49:50Z","timestamp":1558302590000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-40328-6_12"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642403279","9783642403286"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-40328-6_12","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}