Competitive Algorithms for On-line Set Cover or How to Beat Murphy's Law

This paper considers an on-line optimization version of the set cover problem. We present a optimally competitive on-line randomized algorithm which is O(logn log m) competitive where n is the maximum number of sets and m is maximum the number of elements. Moreover, we provide a matching lower bound for the problem. We also give several applications of the results. Randomization is crucial for our result since a deterministic algorithm may cover only one element with each accepted set and thus, cannot achieve any non-trivial bound. 1 Introduction 1.1 The Problem In this paper we consider an on-line version of the following variant of the set cover problem, parameterized by k: Given a family of sets F = fS 1 ; S 2 ; : : : ; S n g, where S i ae fv 1 ; v 2 ; : : : ; v m g, for all i, choose some subset F 0 ae F , where F 0 is of size k, such that the size of the union of all S 2 F 0 is maximized. This paper introduces and optimally solves an on-line version of this problem: Base ..