{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,9]],"date-time":"2024-09-09T16:02:22Z","timestamp":1725897742043},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642315930"},{"type":"electronic","value":"9783642315947"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-31594-7_37","type":"book-chapter","created":{"date-parts":[[2012,6,22]],"date-time":"2012-06-22T17:20:21Z","timestamp":1340385621000},"page":"436-448","source":"Crossref","is-referenced-by-count":3,"title":["Approximating Sparse Covering Integer Programs Online"],"prefix":"10.1007","author":[{"given":"Anupam","family":"Gupta","sequence":"first","affiliation":[]},{"given":"Viswanath","family":"Nagarajan","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"37_CR1","doi-asserted-by":"crossref","unstructured":"Alon, N., Awerbuch, B., Azar, Y., Buchbinder, N., Naor(Seffi), J.: The online set cover problem. In: STOC 2003, pp. 100\u2013105 (2003)","DOI":"10.1145\/780542.780558"},{"issue":"4","key":"37_CR2","doi-asserted-by":"publisher","first-page":"640","DOI":"10.1145\/1198513.1198522","volume":"2","author":"N. Alon","year":"2006","unstructured":"Alon, N., Awerbuch, B., Azar, Y., Buchbinder, N., Naor(Seffi), J.: A general approach to online network optimization problems. ACM Trans. Algorithms\u00a02(4), 640\u2013660 (2006)","journal-title":"ACM Trans. Algorithms"},{"key":"37_CR3","doi-asserted-by":"publisher","DOI":"10.1002\/9780470277331","volume-title":"The Probabilistic Method","author":"N. Alon","year":"2008","unstructured":"Alon, N., Spencer, J.: The Probabilistic Method. Wiley-Interscience, New York (2008)"},{"key":"37_CR4","doi-asserted-by":"crossref","unstructured":"Bansal, N., Buchbinder, N., Naor(Seffi), J.: A primal-dual randomized algorithm for weighted paging. In: FOCS 2007, pp. 507\u2013517 (2007)","DOI":"10.1109\/FOCS.2007.43"},{"key":"37_CR5","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1145\/1374376.1374412","volume-title":"STOC 2008","author":"N. Bansal","year":"2008","unstructured":"Bansal, N., Buchbinder, N., Naor(Seffi)., J.: Randomized competitive algorithms for generalized caching. In: STOC 2008, pp. 235\u2013244. ACM, New York (2008)"},{"key":"37_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"369","DOI":"10.1007\/978-3-642-13036-6_28","volume-title":"Integer Programming and Combinatorial Optimization","author":"N. Bansal","year":"2010","unstructured":"Bansal, N., Korula, N., Nagarajan, V., Srinivasan, A.: On k-Column Sparse Packing Programs. In: Eisenbrand, F., Shepherd, F.B. (eds.) IPCO 2010. LNCS, vol.\u00a06080, pp. 369\u2013382. Springer, Heidelberg (2010)"},{"issue":"2-3","key":"37_CR7","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1561\/0400000024","volume":"3","author":"N. Buchbinder","year":"2007","unstructured":"Buchbinder, N., Naor(Seffi)., J.: The design of competitive online algorithms via a primal-dual approach. Found. Trends Theor. Comput. Sci.\u00a03(2-3), 93\u2013263 (2007)","journal-title":"Found. Trends Theor. Comput. Sci."},{"issue":"2","key":"37_CR8","doi-asserted-by":"publisher","first-page":"270","DOI":"10.1287\/moor.1080.0363","volume":"34","author":"N. Buchbinder","year":"2009","unstructured":"Buchbinder, N., Naor(Seffi)., J.: Online primal-dual algorithms for covering and packing. Math. Oper. Res.\u00a034(2), 270\u2013286 (2009)","journal-title":"Math. Oper. Res."},{"key":"37_CR9","unstructured":"Carr, R.D., Fleischer, L.K., Leung, V.J., Phillips, C.A.: Strengthening integrality gaps for capacitated network design and covering problems. In: SODA 2000, pp. 106\u2013115 (2000)"},{"key":"37_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"355","DOI":"10.1007\/978-3-642-13036-6_27","volume-title":"Integer Programming and Combinatorial Optimization","author":"D. Chakrabarty","year":"2010","unstructured":"Chakrabarty, D., Grant, E., K\u00f6nemann, J.: On Column-Restricted and Priority Covering Integer Programs. In: Eisenbrand, F., Shepherd, F.B. (eds.) IPCO 2010. LNCS, vol.\u00a06080, pp. 355\u2013368. Springer, Heidelberg (2010)"},{"key":"37_CR11","doi-asserted-by":"crossref","unstructured":"Gupta, A., Nagarajan, V.: Approximating sparse covering integer programs online. CoRR, abs\/1205.0175 (2012)","DOI":"10.1007\/978-3-642-31594-7_37"},{"issue":"4","key":"37_CR12","doi-asserted-by":"publisher","first-page":"495","DOI":"10.1016\/j.jcss.2005.05.002","volume":"71","author":"S.G. Kolliopoulos","year":"2005","unstructured":"Kolliopoulos, S.G., Young, N.E.: Approximation algorithms for covering\/packing integer programs. J. Comput. Syst. Sci.\u00a071(4), 495\u2013505 (2005)","journal-title":"J. Comput. Syst. Sci."},{"key":"37_CR13","unstructured":"Korman, S.: On the use of randomness in the online set cover problem. M.Sc. thesis, Weizmann Institute of Science (2005)"},{"key":"37_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"634","DOI":"10.1007\/978-3-642-02927-1_53","volume-title":"Automata, Languages and Programming","author":"C. Koufogiannakis","year":"2009","unstructured":"Koufogiannakis, C., Young, N.E.: Greedy \u0394-Approximation Algorithm for Covering with Arbitrary Constraints and Submodular Cost. In: Albers, S., Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S., Thomas, W. (eds.) ICALP 2009, Part I. LNCS, vol.\u00a05555, pp. 634\u2013652. Springer, Heidelberg (2009)"},{"issue":"1","key":"37_CR15","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1007\/s00453-010-9431-z","volume":"61","author":"D. Pritchard","year":"2011","unstructured":"Pritchard, D., Chakrabarty, D.: Approximability of sparse integer programs. Algorithmica\u00a061(1), 75\u201393 (2011)","journal-title":"Algorithmica"},{"issue":"2","key":"37_CR16","doi-asserted-by":"publisher","first-page":"648","DOI":"10.1137\/S0097539796314240","volume":"29","author":"A. Srinivasan","year":"1999","unstructured":"Srinivasan, A.: Improved approximation guarantees for packing and covering integer programs. SIAM J. Comput.\u00a029(2), 648\u2013670 (1999)","journal-title":"SIAM J. Comput."},{"key":"37_CR17","unstructured":"Srinivasan, A.: New approaches to covering and packing problems. In: SODA 2001, pp. 567\u2013576 (2001)"},{"issue":"3","key":"37_CR18","doi-asserted-by":"publisher","first-page":"609","DOI":"10.1137\/S0097539703434620","volume":"36","author":"A. Srinivasan","year":"2006","unstructured":"Srinivasan, A.: An extension of the Lov\u00e1sz Local Lemma, and its applications to integer programming. SIAM J. Comput.\u00a036(3), 609\u2013634 (2006)","journal-title":"SIAM J. Comput."},{"issue":"6","key":"37_CR19","doi-asserted-by":"publisher","first-page":"525","DOI":"10.1007\/BF01189992","volume":"11","author":"N.E. Young","year":"1994","unstructured":"Young, N.E.: The k-server dual and loose competitiveness for paging. Algorithmica\u00a011(6), 525\u2013541 (1994)","journal-title":"Algorithmica"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages, and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-31594-7_37.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,4]],"date-time":"2021-05-04T08:15:02Z","timestamp":1620116102000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-31594-7_37"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642315930","9783642315947"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-31594-7_37","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}