{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:22:13Z","timestamp":1759638133949},"reference-count":22,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2015,4,4]],"date-time":"2015-04-04T00:00:00Z","timestamp":1428105600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2016,4]]},"DOI":"10.1007\/s00453-015-9995-8","type":"journal-article","created":{"date-parts":[[2015,4,3]],"date-time":"2015-04-03T15:03:08Z","timestamp":1428073388000},"page":"1205-1223","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Shrinking Maxima, Decreasing Costs: New Online Packing and Covering Problems"],"prefix":"10.1007","volume":"74","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","published-online":{"date-parts":[[2015,4,4]]},"reference":[{"issue":"2","key":"9995_CR1","doi-asserted-by":"crossref","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 J. Comput. 39(2), 361\u2013370 (2009)","journal-title":"SIAM J. Comput."},{"key":"9995_CR2","doi-asserted-by":"crossref","unstructured":"Awerbuch, B., Azar, Y., Plotkin, S.A.: Throughput-competitive on-line routing. In: 34th IEEE Annual Symposium on Foundations of Computer Science, pp. 32\u201340 (1993)","DOI":"10.1109\/SFCS.1993.366884"},{"key":"9995_CR3","doi-asserted-by":"crossref","unstructured":"Bateni, M., Hajiaghayi, M., Zadimoghaddam, M.: Submodular secretary problem and extensions. In: 13th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, Volume 6302 of LNCS, pp. 39\u201352 (2010)","DOI":"10.1007\/978-3-642-15369-3_4"},{"issue":"3","key":"9995_CR4","first-page":"178","volume":"7","author":"P Berman","year":"2000","unstructured":"Berman, P.: A $$d\/2$$ d \/ 2 approximation for maximum weight independent set in $$d$$ d -claw free graphs. Nord. J. Comput. 7(3), 178\u2013184 (2000)","journal-title":"Nord. J. Comput."},{"issue":"2","key":"9995_CR5","doi-asserted-by":"crossref","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. 34(2), 270\u2013286 (2009)","journal-title":"Math. Oper. Res."},{"issue":"4","key":"9995_CR6","doi-asserted-by":"crossref","first-page":"837","DOI":"10.1137\/S0097539799356265","volume":"33","author":"C Chekuri","year":"2004","unstructured":"Chekuri, C., Khanna, S.: On multidimensional packing problems. SIAM J. Comput. 33(4), 837\u2013851 (2004)","journal-title":"SIAM J. Comput."},{"key":"9995_CR7","doi-asserted-by":"crossref","unstructured":"Cygan, M.: Improved approximation for 3-dimensional matching via bounded pathwidth local search. In: 54th IEEE Annual Symposium on Foundations of Computer Science, pp. 509\u2013518 (2013)","DOI":"10.1109\/FOCS.2013.61"},{"issue":"4","key":"9995_CR8","doi-asserted-by":"crossref","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 J. Comput. 41(4), 728\u2013746 (2012)","journal-title":"SIAM J. Comput."},{"key":"9995_CR9","doi-asserted-by":"crossref","unstructured":"Feldman, M., Naor, J.S., Schwartz, R.: Improved competitive ratios for submodular secretary problems. In: 14th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, Volume 6845 of LNCS, pp. 218\u2013229 (2011)","DOI":"10.1007\/978-3-642-22935-0_19"},{"issue":"2","key":"9995_CR10","doi-asserted-by":"crossref","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. Int. Stat. Rev. 51(2), 189\u2013206 (1983)","journal-title":"Int. Stat. Rev."},{"key":"9995_CR11","doi-asserted-by":"crossref","first-page":"100","DOI":"10.1016\/0377-2217(84)90053-5","volume":"15","author":"AM Frieze","year":"1984","unstructured":"Frieze, A.M., Clarke, M.R.B.: Approximation algorithms for the $$m$$ m -dimensional 0\u20131 knapsack problem: worst-case and probabilistic analyses. Eur. J. Oper. Res. 15, 100\u2013109 (1984)","journal-title":"Eur. J. Oper. Res."},{"issue":"313","key":"9995_CR12","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1080\/01621459.1966.10502008","volume":"61","author":"JP Gilbert","year":"1966","unstructured":"Gilbert, J.P., Mosteller, F.: Recognizing the maximum of a sequence. J. Am. Stat. Assoc. 61(313), 35\u201373 (1966)","journal-title":"J. Am. Stat. Assoc."},{"issue":"1\u20133","key":"9995_CR13","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1016\/S0166-218X(99)00124-9","volume":"99","author":"MM Halld\u00f3rsson","year":"2000","unstructured":"Halld\u00f3rsson, M.M., Kratochv\u00edl, J., Telle, J.A.: Independent sets with domination constraints. Discrete Appl. Math. 99(1\u20133), 39\u201354 (2000)","journal-title":"Discrete Appl. Math."},{"issue":"2","key":"9995_CR14","doi-asserted-by":"crossref","first-page":"300","DOI":"10.1007\/s00224-012-9408-1","volume":"53","author":"MM Halld\u00f3rsson","year":"2013","unstructured":"Halld\u00f3rsson, M.M., Patt-Shamir, B., Rawitz, D.: Online scheduling with interval conflicts. Theory Comput. Syst. 53(2), 300\u2013317 (2013)","journal-title":"Theory Comput. Syst."},{"issue":"1","key":"9995_CR15","doi-asserted-by":"crossref","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^{1-\\epsilon }$$ n 1 - \u03f5 . Acta Math. 182(1), 105\u2013142 (1999)","journal-title":"Acta Math."},{"issue":"1","key":"9995_CR16","doi-asserted-by":"crossref","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. Comput. Complex. 15(1), 20\u201339 (2006)","journal-title":"Comput. Complex."},{"issue":"4","key":"9995_CR17","doi-asserted-by":"crossref","first-page":"463","DOI":"10.1145\/321906.321909","volume":"22","author":"OH Ibarra","year":"1975","unstructured":"Ibarra, O.H., Kim, C.E.: Fast approximation algorithms for the knapsack and sum of subset problems. J. ACM 22(4), 463\u2013468 (1975)","journal-title":"J. ACM"},{"issue":"2","key":"9995_CR18","doi-asserted-by":"crossref","first-page":"244","DOI":"10.1287\/moor.9.2.244","volume":"9","author":"MJ Magazine","year":"1984","unstructured":"Magazine, M.J., Chern, M.-S.: A note on approximation schemes for multidimensional knapsack problems. Math. Oper. Res. 9(2), 244\u2013247 (1984)","journal-title":"Math. Oper. Res."},{"key":"9995_CR19","doi-asserted-by":"crossref","first-page":"12","DOI":"10.1016\/j.tcs.2014.02.019","volume":"530","author":"Y Mansour","year":"2014","unstructured":"Mansour, Y., Patt-Shamir, B., Rawitz, D.: Competitive router scheduling with structured data. Theor. Comput. Sci. 530, 12\u201322 (2014)","journal-title":"Theor. Comput. Sci."},{"issue":"4","key":"9995_CR20","doi-asserted-by":"crossref","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 7(4), 365\u2013374 (1987)","journal-title":"Combinatorica"},{"issue":"1","key":"9995_CR21","doi-asserted-by":"crossref","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. J. ACM 22(1), 115\u2013124 (1975)","journal-title":"J. ACM"},{"key":"9995_CR22","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":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-015-9995-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-015-9995-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-015-9995-8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,28]],"date-time":"2019-05-28T23:47:23Z","timestamp":1559087243000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-015-9995-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,4,4]]},"references-count":22,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2016,4]]}},"alternative-id":["9995"],"URL":"https:\/\/doi.org\/10.1007\/s00453-015-9995-8","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,4,4]]}}}