arXiv preprint ·
A Tight $\widetilde Ω(\sqrt{m})$ Information-Theoretic Lower Bound for Randomized Online Set Cover
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
Online set cover is a fundamental problem in online algorithms, admitting a deterministic $O(\log m\log n)$-competitive algorithm, where $m$ is the number of sets and $n$ is the number of elements. This is essentially tight for deterministic algorithms as well as for polynomial-time randomized algorithms assuming $\mathrm{NP}\not\subseteq\mathrm{BPP}$. However, the best lower bound known for information-theoretic (computationally unlimited) randomized algorithms against an oblivious adversary is only $Ω(\log m)$, whereas the upper bound in terms of $m$ is $O(\sqrt m\log m)=\widetilde O(\sqrt m)$. We prove an $Ω(\sqrt m)$ lower bound for information-theoretic randomized unweighted online set cover, showing that even with unbounded computational power, randomization cannot achieve an $O(\log m)$-competitive ratio. Specifically, our lower bound rules out $O(\log m\cdot\log^{1/2-\varepsilon} n)$-competitive algorithms for every constant $\varepsilon>0$. Our techniques also prove an $Ω(m^{1/3})$ lower bound in the random-order model, and show that every algorithm with $poly(m)$ memory has competitive ratio $Ω(m/\log m)$, even with unlimited computation between requests.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Quasi-Monte Carlo Beyond Hardy-Krause II: $(1 + \varepsilon)n$ Samples Suffice
Spatial Mixing and Deterministic Approximate Counting of Multi-spin Systems beyond Bounded Degree Graphs
A deterministic $(1+\varepsilon)^n$ approximation for the permanent of a nonnegative matrix
Differential Privacy Meets Fixed Parameter Tractability: Algorithms and Lower Bounds
Single-Exponential Algorithms and a Polynomial Kernel for Strong Connectivity Augmentation
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.