In the stochastic set cover problem (Grandoni et al., FOCS '08), we are given a collection $\mathcal{S}$ of $m$ sets over a universe $\mathcal{U}$ of size $N$, and a distribution $D$ over elements of $\mathcal{U}$. The algorithm draws $n$ elements one-by-one from $D$ and must buy a set to cover each element on arrival; the goal is to minimize the total cost of sets bought during this process. A universal algorithm a priori maps each element $u \in \mathcal{U}$ to a set $S(u)$ such that if $U \subseteq \mathcal{U}$ is formed by drawing $n$ times from distribution $D$, then the algorithm commits to outputting $S(U)$. Grandoni et al. gave an $O(\log mN)$-competitive universal algorithm for this stochastic set cover problem. We improve unilaterally upon this result by giving a simple, polynomial time $O(\log mn)$-competitive universal algorithm for the more general prophet version, in which $U$ is formed by drawing from $n$ different distributions $D_1, \ldots, D_n$. Furthermore, we show that we do not need full foreknowledge of the distributions: in fact, a single sample from each distribution suffices. We show similar results for the 2-stage prophet setting and for the online-with-a-sample setting. We obtain our results via a generic reduction from the single-sample prophet setting to the random-order setting; this reduction holds for a broad class of minimization problems that includes all covering problems. We take advantage of this framework by giving random-order algorithms for non-metric facility location and set multicover; using our framework, these automatically translate to universal prophet algorithms.
翻译:闭眼做盖集问题
摘要:在随机盖集问题(Grandoni等,FOCS '08)中,我们得到了一个大小为$N$的宇宙$U$集合${\mathcal{S}}$和分布$D$。算法逐个从$D$中抽取$n$个元素,并必须购买一组以覆盖到达的每个元素。目标是最小化过程中购买的集合的总成本。先验通用算法将每个元素$u\in U$映射到集合$S(u)$,使得如果从分布$D$抽样$n$次形成集合$U\subseteq U$,则该算法将输出$S(U)$。Grandoni等人为这个随机盖集问题提供了一个$O(\log mN)$竞争性的通用算法。我们通过为更一般的先知版本提供一个简单的多项式时间$O(\log mn)$竞争性的通用算法,一方面改进了这个结果,在这个更一般的版本中,$U$是从$n$不同的分布$D_1,\ldots,D_n$中抽取的。此外,我们还表明,我们不需要分布的完全预知:事实上,每个分布的一个样本就足够了。我们展示了类似的结果适用于2阶段先知设置和在线样本设置。我们通过从单样本先知设置到随机序列设置的通用缩减来获得我们的结果;这个缩减对广泛的最小化问题类都适用,包括所有覆盖问题。我们利用这个框架给出了非度量设施选址和集合多重覆盖的随机序列算法;使用我们的框架,这些自动转化为通用先知算法。