# The online set cover problem

Noga Alon, Baruch Awerbuch, Yossi Azar, Niv Buchbinder, Joseph Naor

Research output: Contribution to journalConference articlepeer-review

108 Scopus citations

## Abstract

Let X = {1, 2, . . . , n} be a ground set of n elements, and let S be a family of subsets of X, |S| = m, with a positive cost cS associated with each S ∈ 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 S containing it. We assume that the elements of X and the members of S are known in advance to the algorithm, however, the set X′ ⊆ 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 C denote the family of sets in S that the algorithm chooses. At the end of the game the adversary also produces (off-line) a family of sets COPT that covers X′. The performance of the algorithm is the ratio between the cost of C and the cost of COPT. 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 Ω (log n log m/log log m+log log n) 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 the fractional solution they supply into a deterministic online algorithm.

Original language English (US) 100-105 6 Conference Proceedings of the Annual ACM Symposium on Theory of Computing Published - 2003 Yes 35th Annual ACM Symposium on Theory of Computing - San Diego, CA, United StatesDuration: Jun 9 2003 → Jun 11 2003

• Software

## Keywords

• Competitive Analysis
• Derandomization
• On-line Algorithms
• Randomized Rounding
• Set-Cover

## Fingerprint

Dive into the research topics of 'The online set cover problem'. Together they form a unique fingerprint.
{"ft_lang_label":"__label__en","ft_lang_prob":0.91475517,"math_prob":0.80680543,"size":2082,"snap":"2023-40-2023-50","text_gpt3_token_len":492,"char_repetition_ratio":0.12848893,"word_repetition_ratio":0.021857923,"special_character_ratio":0.23487031,"punctuation_ratio":0.09022556,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.97222567,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2023-12-08T16:16:05Z\",\"WARC-Record-ID\":\"<urn:uuid:a2ef49ba-a7b4-41b1-9298-fc0aa65b315b>\",\"Content-Length\":\"44452\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:edf3d3af-80d7-4d4a-b21f-9fd8afe292a9>\",\"WARC-Concurrent-To\":\"<urn:uuid:927e503f-52a7-4f56-a319-7004519549e5>\",\"WARC-IP-Address\":\"18.210.30.88\",\"WARC-Target-URI\":\"https://collaborate.princeton.edu/en/publications/the-online-set-cover-problem\",\"WARC-Payload-Digest\":\"sha1:WERNJMV5GOP6MCLPUET4VNQPMKPWITPW\",\"WARC-Block-Digest\":\"sha1:AGFTRQKRHJ6HMFP5HUR3L65GCIPAYC2U\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2023/CC-MAIN-2023-50/CC-MAIN-2023-50_segments_1700679100762.64_warc_CC-MAIN-20231208144732-20231208174732-00423.warc.gz\"}"}