{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T06:20:52Z","timestamp":1725603652957},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642237188"},{"type":"electronic","value":"9783642237195"}],"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-23719-5_30","type":"book-chapter","created":{"date-parts":[[2011,8,30]],"date-time":"2011-08-30T13:14:33Z","timestamp":1314710073000},"page":"347-357","source":"Crossref","is-referenced-by-count":1,"title":["Hitting Sets Online and Vertex Ranking"],"prefix":"10.1007","author":[{"given":"Guy","family":"Even","sequence":"first","affiliation":[]},{"given":"Shakhar","family":"Smorodinsky","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"30_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.S.: The Online Set Cover Problem. SIAM Journal on Computing\u00a039, 361 (2009)","journal-title":"SIAM Journal on Computing"},{"key":"30_CR2","volume-title":"Online computation and competitive analysis","author":"A. Borodin","year":"1998","unstructured":"Borodin, A., El-Yaniv, R.: Online computation and competitive analysis, vol.\u00a02. Cambridge University Press, Cambridge (1998)"},{"issue":"1","key":"30_CR3","doi-asserted-by":"publisher","first-page":"463","DOI":"10.1007\/BF02570718","volume":"14","author":"H. Br\u00f6nnimann","year":"1995","unstructured":"Br\u00f6nnimann, H., Goodrich, M.T.: Almost optimal set covers in finite VC-dimension. Discrete and Computational Geometry\u00a014(1), 463\u2013479 (1995)","journal-title":"Discrete and Computational Geometry"},{"key":"30_CR4","first-page":"515","volume-title":"Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms","author":"B. Ben-Moshe","year":"2005","unstructured":"Ben-Moshe, B., Katz, M.J., Mitchell, J.S.B.: A constant-factor approximation algorithm for optimal terrain guarding. In: Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 515\u2013524. SIAM, Philadelphia (2005)"},{"issue":"3","key":"30_CR5","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1287\/moor.4.3.233","volume":"4","author":"V. Chvatal","year":"1979","unstructured":"Chvatal, V.: A greedy heuristic for the set-covering problem. Mathematics of Operations Research\u00a04(3), 233\u2013235 (1979)","journal-title":"Mathematics of Operations Research"},{"issue":"1","key":"30_CR6","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1007\/s00454-006-1273-8","volume":"37","author":"K.L. Clarkson","year":"2007","unstructured":"Clarkson, K.L., Varadarajan, K.: Improved approximation algorithms for geometric set cover. Discrete and Computational Geometry\u00a037(1), 43\u201358 (2007)","journal-title":"Discrete and Computational Geometry"},{"key":"30_CR7","doi-asserted-by":"publisher","first-page":"94","DOI":"10.1137\/S0097539702431840","volume":"33","author":"G. Even","year":"2003","unstructured":"Even, G., Lotker, Z., Ron, D., Smorodinsky, S.: Conflict-Free Colorings of Simple Geometric Regions with Applications to Frequency Assignment in Cellular Networks. SIAM Journal on Computing\u00a033, 94\u2013136 (2003)","journal-title":"SIAM Journal on Computing"},{"issue":"2","key":"30_CR8","doi-asserted-by":"publisher","first-page":"358","DOI":"10.1016\/j.ipl.2005.03.010","volume":"95","author":"G. Even","year":"2005","unstructured":"Even, G., Rawitz, D., Shahar, S.M.: Hitting sets when the VC-dimension is small. Information Processing Letters\u00a095(2), 358\u2013362 (2005)","journal-title":"Information Processing Letters"},{"issue":"4","key":"30_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 (JACM)\u00a045(4), 634\u2013652 (1998)","journal-title":"Journal of the ACM (JACM)"},{"issue":"1","key":"30_CR10","doi-asserted-by":"publisher","first-page":"136","DOI":"10.1145\/2455.214106","volume":"32","author":"D.S. Hochbaum","year":"1985","unstructured":"Hochbaum, D.S., Maass, W.: Approximation schemes for covering and packing problems in image processing and VLSI. Journal of the ACM (JACM)\u00a032(1), 136 (1985)","journal-title":"Journal of the ACM (JACM)"},{"issue":"5","key":"30_CR11","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1016\/0020-0190(88)90194-9","volume":"28","author":"A.V. Iyer","year":"1988","unstructured":"Iyer, A.V., Ratliff, H.D., Vijayan, G.: Optimal node ranking of trees. Information Processing Letters\u00a028(5), 225\u2013229 (1988)","journal-title":"Information Processing Letters"},{"issue":"3","key":"30_CR12","doi-asserted-by":"publisher","first-page":"256","DOI":"10.1016\/S0022-0000(74)80044-9","volume":"9","author":"D.S. Johnson","year":"1974","unstructured":"Johnson, D.S.: Approximation algorithms for combinatorial problems. Journal of Computer and System Sciences\u00a09(3), 256\u2013278 (1974)","journal-title":"Journal of Computer and System Sciences"},{"key":"30_CR13","doi-asserted-by":"crossref","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: Proc. Sympos., IBM Thomas J. Watson Res. Center, Yorktown Heights, NY, pp. 85\u2013103 (1972)","DOI":"10.1007\/978-1-4684-2001-2_9"},{"issue":"1-3","key":"30_CR14","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1016\/0012-365X(93)E0216-Q","volume":"142","author":"M. Katchalski","year":"1995","unstructured":"Katchalski, M., McCuaig, W., Seager, S.: Ordered colourings. Discrete Mathematics\u00a0142(1-3), 141\u2013154 (1995)","journal-title":"Discrete Mathematics"},{"key":"30_CR15","doi-asserted-by":"crossref","first-page":"445","DOI":"10.1145\/301250.301369","volume-title":"Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing","author":"V.S.A. Kumar","year":"1999","unstructured":"Kumar, V.S.A., Ramesh, H.: Covering rectilinear polygons with axis-parallel rectangles. In: Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, pp. 445\u2013454. ACM, New York (1999)"},{"issue":"4","key":"30_CR16","doi-asserted-by":"publisher","first-page":"327","DOI":"10.1016\/0167-8191(86)90014-1","volume":"3","author":"J.W.H. Liu","year":"1986","unstructured":"Liu, J.W.H.: Computational models and task scheduling for parallel sparse cholesky factorization. Parallel Computing\u00a03(4), 327\u2013342 (1986)","journal-title":"Parallel Computing"},{"issue":"2","key":"30_CR17","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1016\/0020-0190(89)90161-0","volume":"33","author":"A.A. Sch\u00e4ffer","year":"1989","unstructured":"Sch\u00e4ffer, A.A.: Optimal node ranking of trees in linear time. Information Processing Letters\u00a033(2), 91\u201396 (1989)","journal-title":"Information Processing Letters"},{"issue":"2","key":"30_CR18","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1016\/0020-0190(92)90017-P","volume":"43","author":"A. Sen","year":"1992","unstructured":"Sen, A., Deng, H., Guha, S.: On a graph partition problem with application to VLSI layout. Information Processing Letters\u00a043(2), 87\u201394 (1992)","journal-title":"Information Processing Letters"},{"issue":"2","key":"30_CR19","doi-asserted-by":"publisher","first-page":"202","DOI":"10.1145\/2786.2793","volume":"28","author":"D.D. Sleator","year":"1985","unstructured":"Sleator, D.D., Tarjan, R.E.: Amortized efficiency of list update and paging rules. Communications of the ACM\u00a028(2), 202\u2013208 (1985)","journal-title":"Communications of the ACM"}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2013 ESA 2011"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-23719-5_30","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,12,2]],"date-time":"2021-12-02T08:14:46Z","timestamp":1638432886000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-23719-5_30"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642237188","9783642237195"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-23719-5_30","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}