The online set cover problem

DOI10.1145/780542.780558MaRDI QIDQ3581267zbMATH OpenOpenAlexFDO

Authors Noga Alon, Baruch Awerbuch, Yossi Azar

Publication date 16 August 2010

Published in Proceedings of the thirty-fifth annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/780542.780558

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Analysis of algorithms (68W40) Combinatorial optimization (90C27)

Recommendations

• The online set cover problem
• Greedy algorithms for on-line set-covering
• Approximating the online set multicover problems via randomized winnowing
• Algorithms and Data Structures
• Online and dynamic algorithms for set cover

Cited in

(28)

• Online set multicover algorithms for dynamic D2D communications
• Robust multicovers with budgeted uncertainty
• Online variable sized covering
• Online budgeted maximum coverage
• Viral marketing of online game by DS decomposition in social networks
• The online set aggregation problem
• Approximating the online set multicover problems via randomized winnowing
• Greedy algorithms for on-line set-covering
• Randomized online algorithms for set cover leasing problems
• Efficient on-line algorithm for maintaining k-cover of sparse bit-strings
• scientific article; zbMATH DE number 6696496 (Why is no real title available?)
• Pick, pack, \& survive: charging robots in a modern warehouse based on online connected dominating sets
• The covert set-cover problem with application to network discovery
• The online set cover problem
• scientific article; zbMATH DE number 1305443 (Why is no real title available?)
• Online maximum \(k\)-coverage
• Online budgeted maximum coverage
• Online and dynamic algorithms for set cover
• Online disjoint set cover without prior knowledge
• Online Dominating Set
• Competitive analysis via regularization
• Algorithms and Data Structures
• Algorithms – ESA 2005
• Adversarial bandits with knapsacks
• Chasing convex bodies optimally
• Nonlinear paging
• Approximation algorithm for prize-collecting weighted set cover with fairness constraints
• Non-cooperative cost sharing games via subsidies

This page was built for publication: The online set cover problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3581267)