Academic
Publications
The online set cover problem

The online set cover problem,10.1145/780542.780558,Noga Alon,Baruch Awerbuch,Yossi Azar,Niv Buchbinder,Joseph Naor

The online set cover problem   (Citations: 45)
BibTex | RIS | RefWorks Download
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.
Conference: ACM Symposium on Theory of Computing - STOC , vol. 39, no. 2, pp. 100-105, 2003
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
    • ...For this problem, Alon et al. [2] gave an O(logn logm)-competitive algorithm, and showed that no deterministic algorithm can achieve a worst-case competitive ratio better than (...

    Mohammad Mahdianet al. Online Optimization with Uncertain Information

    • ...Linear programming relaxations have been used in the past in the competitive analysis of on-line algorithms, most notably in the on-line primal-dual schema introduced in [4, 9, 16] (see also [8] for additional references)...

    Noa Avigdor-Elgrabliet al. An Improved Competitive Algorithm for Reordering Buffer Management

    • ...This approach was applied to online set cover [1], and to the following variant of packing: In each step, a new set is introduced by listing all its elements; the algorithm may accept the set only if it is disjoint to previously accepted sets, but it may also reject it. If a set is accepted, the algorithm collects the set value immediately...
    • ...Denote by rmax the maximum priority among the priorities of sets in N(S), i.e., rmax = maxS′∈N(S) r(S ′ ). By independence of r(S ′ ) for different sets in N(S) we have, for x ∈ [0,1], that...

    Yuval Emeket al. Online set packing and competitive scheduling of multi-part tasks

    • ...In [3], Alon et al. also study approximation algorithms for the Online Set Cover problem, which has connections to Network Inference problems which we explore in this paper...

    Dana Angluinet al. Inferring Social Networks from Outbreaks

    • ...In order to design mechanisms for both the fractional and integral models, we draw on ideas from [1, 4]. In [1] Alon et al. considered an online version of the set cover problem, where elements arrive one by one and need to be covered upon arrival...
    • ...In order to design mechanisms for both the fractional and integral models, we draw on ideas from [1, 4]. In [1] Alon et al. considered an online version of the set cover problem, where elements arrive one by one and need to be covered upon arrival...
    • ...The goal of [1] is to design an online algorithm achieving the best possible competitive ratio with respect to the optimal solution, i.e., optimal social welfare...
    • ...In [1], an O(log m log n)-competitive algorithm is presented for this online setting...
    • ...We thus go beyond the online version of the set cover problem considered in [1], and analyze its non-cooperative game extension...
    • ...The model investigated in [1] can be seen as a special case of ours, where the central authority pays for the full cost of the cover and users pay nothing...
    • ...(Also, users join one by one without reaching equilibrium.) Thus, using the algorithm of [1], a central authority will not be able to finance the subsidies from taxes...
    • ...almost matches the lower bound of �( log m log n log log m+log log n ) shown in [1] for the online setting...
    • ...As in [1], we maintain a fractional primal solution, however, in our case, it is not always feasible...
    • ...In [1], Alon et al. obtained an integral solution for their online setting by maintaining at each iteration a fractional feasible solution and using a potential function that determines which of the sets should be chosen to the integral cover...
    • ...We design a new potential function and note that the potential function defined in [1] cannot satisfy our needs, as it would lead to a high taxation ratio...

    Niv Buchbinderet al. Non-Cooperative Cost Sharing Games via Subsidies

Sort by: