When the Optimum is also Blind: a New Perspective on Universal Optimization

Marek Adamczyk, Fabrizio Grandoni, Stefano Leonardi +1

Consider the following variant of the set cover problem. We are given a universe $U=\{1,...,n\}$ and a collection of subsets $\mathcal{C}=\{S_1,...,S_m\}$ where $S_i\subseteq U$…