Information theory sets limits on randomized online set cover
An $\tilde Ω(\log n \log m)$ Information-Theoretic Lower Bound for Randomized Online Set Cover
Data Structures and Algorithms
Summary
The paper finds a new mathematical lower bound on the difficulty of a problem called online set cover, where elements need to be covered by sets that are chosen one by one without knowing future items. The authors show that any randomized method for this problem must use at least a certain amount of information, specifically on the order of logarithms of the number of elements and sets. This means there is a fundamental limit on how efficiently these problems can be solved in an online setting. The result holds under broad conditions on the number of elements and sets involved.
What this means in practice
- •For algorithm designers: Avoid designing randomized online set cover algorithms aiming to surpass the established information-theoretic lower bound.
- •For complexity analysts: Use the lower bound to evaluate feasibility and limits in online combinatorial optimization problems involving large ground sets and collections.
A theory result. No direct application yet.
Authors
Roie Levin
Abstract
We show an information-theoretic lower bound of $Ω\left(\frac{\log n \log m}{\log \log n + \log \log m}\right)$ for online set cover against randomized algorithms, for all sufficiently large $m$ and $n$ satisfying $\log^2 n \leq m \leq 2^n$.