{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:26:40Z","timestamp":1787340400694,"version":"build-2736575974"},"reference-count":17,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2009,1]]},"abstract":"<jats:p>Let $X=\\{1,2,\\ldots,n\\}$ be a ground set of n elements, and let ${\\cal S}$ be a family of subsets of X, $|{\\cal S}|=m$, with a positive cost $c_S$ associated with each $S\\in{\\cal S}$. Consider the following online version of the set cover problem, described as a game between an algorithm and an adversary. An adversary gives elements to the algorithm from X one by one. Once a new element is given, the algorithm has to cover it by some set of ${\\cal S}$ containing it. We assume that the elements of X and the members of ${\\cal S}$ are known in advance to the algorithm; however, the set $X'\\subseteq X$ of elements given by the adversary is not known in advance to the algorithm. (In general, $X'$ may be a strict subset of X.) The objective is to minimize the total cost of the sets chosen by the algorithm. Let ${\\cal C}$ denote the family of sets in ${\\cal S}$ that the algorithm chooses. At the end of the game the adversary also produces (offline) a family of sets ${\\cal C}_{OPT}$ that covers $X'$. The performance of the algorithm is the ratio between the cost of ${\\cal C}$ and the cost of ${\\cal C}_{OPT}$. The maximum ratio, taken over all input sequences, is the competitive ratio of the algorithm. We present an $O(\\log m\\log n)$ competitive deterministic algorithm for the problem and establish a nearly matching $\\Omega\\bigl(\\frac{\\log n\\log m}{\\log\\log m+\\log\\log n}\\bigr)$ lower bound for all interesting values of m and n. The techniques used are motivated by similar techniques developed in computational learning theory for online prediction (e.g., the WINNOW algorithm) together with a novel way of converting a fractional solution into a deterministic online algorithm.<\/jats:p>","DOI":"10.1137\/060661946","type":"journal-article","created":{"date-parts":[[2009,6,3]],"date-time":"2009-06-03T18:07:36Z","timestamp":1244052456000},"page":"361-370","source":"Crossref","is-referenced-by-count":81,"title":["The Online Set Cover Problem"],"prefix":"10.1137","volume":"39","author":[{"given":"Noga","family":"Alon","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Baruch","family":"Awerbuch","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yossi","family":"Azar","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Niv","family":"Buchbinder","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Joseph (Seffi)","family":"Naor","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2009,6,3]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","unstructured":"N. Alon, B. Awerbuch, Y. Azar, N. Buchbinder, and J. Naor,\n                      The online set cover problem\n                      , in Proceedings of the 35th Annual ACM Symposium on the Theory of Computation (San Diego, 2003), ACM, New York, 2003, pp. 100\u2013105.","DOI":"10.1145\/780542.780558"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1145\/1198513.1198522"},{"key":"R3","doi-asserted-by":"crossref","unstructured":"B. Awerbuch, Y. Azar, A. Fiat, and T. Leighton,\n                      Making commitments in the face of uncertainty: How to pick a winner almost every time\n                      , in Proceedings of the 28th Annual ACM Symposium on the Theory of Computation (Philadelphia, 1996), ACM, New York, 1996, pp. 519\u2013530.","DOI":"10.1145\/237814.238000"},{"key":"R4","doi-asserted-by":"crossref","unstructured":"N. Bansal, N. Buchbinder, and J. Naor,\n                      A primal-dual randomized algorithm for weighted paging\n                      , in Proceedings of the 48rd Annual IEEE Symposium on Foundations of Computer Science (Providence, RI, 2007), IEEE Press, Piscataway, NJ, pp. 507\u2013517.","DOI":"10.1109\/FOCS.2007.43"},{"key":"R5","doi-asserted-by":"crossref","unstructured":"A. Blum,\n                      On-line algorithms in machine learning\n                      , in Online Algorithms: The State of the Art, A. Fiat and G. Woeginger, eds., Lecture Notes in Comput. Sci. 1442, Springer, New York, 1998, Chapter 14, pp. 306\u2013325.","DOI":"10.1007\/BFb0029575"},{"key":"R6","unstructured":"A. Blum,\n                      Online learning tools for online algorithms\n                      , Dagstuhl Workshop on Online Algorithms, 2002; available online at http:\/\/www-2.cs.cmu.edu\/~avrim\/surveys.html."},{"key":"R7","unstructured":"A. Blum, S. Chawla, and A. Kalai,\n                      Static optimality and dynamic search-optimality in lists and trees\n                      , in Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms (San Francisco, CA, 2002), SIAM, Philadelphia, 2002, pp. 1\u20138."},{"key":"R8","doi-asserted-by":"crossref","unstructured":"N. Buchbinder and J. Naor,\n                      Online primal-dual algorithms for covering and packing problems\n                      , in Proceedings of the 13th Annual European Symposium on Algorithms (Palma de Mallorca, Spain, 2005), Lecture Notes in Comput. Sci. 3669, Springer, New York, 2005, pp. 689\u2013701. Math. Oper. Res., to appear.","DOI":"10.1007\/11561071_61"},{"key":"R9","doi-asserted-by":"crossref","unstructured":"N. Buchbinder, K. Jain, and J. Naor,\n                      Online primal-dual algorithms for maximizing ad-auctions revenue\n                      , in Proceedings of the 15th Annual European Symposium on Algorithms (Eilat, Israel, 2007), Lecture Notes in Comput. Sci. 4698, Springer, New York, 2007, pp. 253\u2013264.","DOI":"10.1007\/978-3-540-75520-3_24"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1287\/moor.4.3.233"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1145\/285055.285059"},{"key":"R12","doi-asserted-by":"crossref","unstructured":"Y. Freund and R. E. Schapire,\n                      Game theory, on-line prediction and boosting\n                      , in Proceedings of the 9th Annual Conference on Computational Learning Theory (Desenzano del Garda, Italy, 1996), ACM, New York, 1996, pp. 325\u2013332.","DOI":"10.1145\/238061.238163"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(74)80044-9"},{"key":"R14","doi-asserted-by":"crossref","unstructured":"A. R. Karlin, C. Kenyon, and D. Randall,\n                      Dynamic TCP acknowledgement and other stories about e\/(e-1)\n                      , in Proceedings of the 28th Annual ACM Symposium on the Theory of Computation (Heraklion, Crete, Greece, 2001), ACM, New York, 2001, pp. 502\u2013509.","DOI":"10.1145\/380752.380845"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1994.1009"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(75)90058-8"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1145\/185675.306789"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/060661946","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:33:21Z","timestamp":1787337201000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/060661946"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,1]]},"references-count":17,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2009,1]]}},"alternative-id":["10.1137\/060661946"],"URL":"https:\/\/doi.org\/10.1137\/060661946","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,1]]}}}