Sign in
Author

Conference

Journal

Organization

Year

DOI
Look for results that meet for the following criteria:
since
equal to
before
between
and
Search in all fields of study
Limit my searches in the following fields of study
Agriculture Science
Arts & Humanities
Biology
Chemistry
Computer Science
Economics & Business
Engineering
Environmental Sciences
Geosciences
Material Science
Mathematics
Medicine
Physics
Social Science
Multidisciplinary
Keywords
(9)
Competitive Analysis
Competitive Ratio
Computational Learning Theory
Online Algorithm
Online Algorithm
Randomized Rounding
Set Cover
Set Covering Problem
Lower Bound
Related Publications
(12)
A general approach to online network optimization problems
Online PrimalDual Algorithms for Covering and Packing Problems
Admission control to minimize rejections and online set cover with repetitions
The Design of Competitive Online Algorithms via a PrimalDual Approach
A PrimalDual Algorithm for Online Nonuniform Facility Location
Subscribe
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
Edit
The online set cover problem
(
Citations: 45
)
BibTex

RIS

RefWorks
Download
Noga Alon
,
Baruch Awerbuch
,
Yossi Azar
,
Niv Buchbinder
,
Joseph Naor
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 onebyone. 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 (offline) 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. 100105, 2003
DOI:
10.1145/780542.780558
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.
(
portal.acm.org
)
(
portal.acm.org
)
(
portal.acm.org
)
(
dx.doi.org
)
(
www.informatik.unitrier.de
)
(
doi.acm.org
)
(
www.informatik.unitrier.de
)
More »
Citation Context
(31)
...For this problem, Alon et al. [
2
] gave an O(logn logm)competitive algorithm, and showed that no deterministic algorithm can achieve a worstcase competitive ratio better than (...
Mohammad Mahdian
,
et al.
Online Optimization with Uncertain Information
...Linear programming relaxations have been used in the past in the competitive analysis of online algorithms, most notably in the online primaldual schema introduced in [
4
, 9, 16] (see also [8] for additional references)...
Noa AvigdorElgrabli
,
et 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 Emek
,
et al.
Online set packing and competitive scheduling of multipart 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 Angluin
,
et 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 noncooperative 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 Buchbinder
,
et al.
NonCooperative Cost Sharing Games via Subsidies
References
(15)
Approximation Algorithms for Combinatorial Problems
(
Citations: 1010
)
David S. Johnson
Journal:
Journal of Computer and System Sciences  JCSS
, vol. 9, no. 3, pp. 256278, 1974
The Weighted Majority Algorithm
(
Citations: 781
)
Nicholas Littlestone
,
Manfred K. Warmuth
Journal:
Information and Computation/information and Control  IANDC
, vol. 108, no. 2, pp. 212261, 1994
Making Commitments in the Face of Uncertainty: How to Pick a Winner Almost Every Time
(
Citations: 61
)
Baruch Awerbuch
,
Yossi Azar
,
Amos Fiat
,
Frank Thomson Leighton
Conference:
ACM Symposium on Theory of Computing  STOC
, 1996
Online Algorithms in Machine Learning
(
Citations: 70
)
Avrim Blum
Journal:
Lecture Notes in Computer Science  LNCS
, vol. 1442, pp. 306325, 1996
A threshold of ln n for approximating set cover
(
Citations: 931
)
Uriel Feige
Journal:
Journal of The ACM  JACM
, vol. 45, no. 4, pp. 634652, 1998
Sort by:
Citations
(45)
Online Optimization with Uncertain Information
Mohammad Mahdian
,
Hamid Nazerzadeh
,
Amin Saberi
Journal:
ACM Transactions on Algorithms  TALG
, pp. 129, 2012
Online and incremental algorithms for facility location
Dimitris Fotakis
Journal:
Sigact News  SIGACT
, vol. 42, no. 1, pp. 97131, 2011
An Improved Competitive Algorithm for Reordering Buffer Management
(
Citations: 3
)
Noa AvigdorElgrabli
,
Yuval Rabani
Conference:
ACMSIAM Symposium on Discrete Algorithms  SODA
, pp. 1321, 2010
Online set packing and competitive scheduling of multipart tasks
(
Citations: 1
)
Yuval Emek
,
Magnús M. Halldórsson
,
Yishay Mansour
,
Boaz PattShamir
,
Jaikumar Radhakrishnan
,
Dror Rawitz
Conference:
Symposium on Principles of Distributed Computing  PODC
, pp. 440449, 2010
Inferring Social Networks from Outbreaks
(
Citations: 1
)
Dana Angluin
,
James Aspnes
,
Lev Reyzin
Conference:
Algorithmic Learning Theory  ALT
, pp. 104118, 2010