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阶段先知设置和在线样本设置。我们通过从单样本先知设置到随机序列设置的通用缩减来获得我们的结果;这个缩减对广泛的最小化问题类都适用,包括所有覆盖问题。我们利用这个框架给出了非度量设施选址和集合多重覆盖的随机序列算法;使用我们的框架,这些自动转化为通用先知算法。

0
下载
关闭预览

相关内容

在数学和计算机科学之中,算法(Algorithm)为一个计算的具体步骤,常用于计算、数据处理和自动推理。精确而言,算法是一个表示为有限长列表的有效方法。算法应包含清晰定义的指令用于计算函数。 来自维基百科: 算法
【ICML2022】GALAXY:极化图主动学习
专知会员服务
30+阅读 · 2022年6月12日
专知会员服务
14+阅读 · 2021年9月23日
专知会员服务
20+阅读 · 2021年8月1日
专知会员服务
24+阅读 · 2021年6月15日
专知会员服务
25+阅读 · 2021年5月23日
【2020 最新论文】对比学习中什么应该不是对比的?
专知会员服务
38+阅读 · 2020年8月16日
寻找领域不变量:从生成模型到因果表征
PaperWeekly
1+阅读 · 2022年10月11日
生成扩散模型漫谈:最优扩散方差估计(上)
PaperWeekly
0+阅读 · 2022年9月25日
WWW 2022 | 可扩展的图随机神经网络
PaperWeekly
0+阅读 · 2022年8月26日
CIKM2022 | CROLoss: 一种推荐系统中检索模型的可定制损失函数
机器学习与推荐算法
2+阅读 · 2022年8月10日
生成扩散模型漫谈:DDPM = 贝叶斯 + 去噪
PaperWeekly
1+阅读 · 2022年7月24日
从重参数的角度看离散概率分布的构建
PaperWeekly
0+阅读 · 2022年5月28日
从泰勒展开来看梯度下降算法
深度学习每日摘要
13+阅读 · 2019年4月9日
机器学习常见模式LogSumExp解密
论智
21+阅读 · 2018年10月30日
变分自编码器VAE:一步到位的聚类方案
PaperWeekly
25+阅读 · 2018年9月18日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
3+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
1+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2008年12月31日
Parallel Sampling of Diffusion Models
Arxiv
0+阅读 · 2023年5月25日
Arxiv
0+阅读 · 2023年5月25日
Arxiv
0+阅读 · 2023年5月22日
Arxiv
11+阅读 · 2018年1月18日
VIP会员
相关VIP内容
【ICML2022】GALAXY:极化图主动学习
专知会员服务
30+阅读 · 2022年6月12日
专知会员服务
14+阅读 · 2021年9月23日
专知会员服务
20+阅读 · 2021年8月1日
专知会员服务
24+阅读 · 2021年6月15日
专知会员服务
25+阅读 · 2021年5月23日
【2020 最新论文】对比学习中什么应该不是对比的?
专知会员服务
38+阅读 · 2020年8月16日
相关资讯
寻找领域不变量:从生成模型到因果表征
PaperWeekly
1+阅读 · 2022年10月11日
生成扩散模型漫谈:最优扩散方差估计(上)
PaperWeekly
0+阅读 · 2022年9月25日
WWW 2022 | 可扩展的图随机神经网络
PaperWeekly
0+阅读 · 2022年8月26日
CIKM2022 | CROLoss: 一种推荐系统中检索模型的可定制损失函数
机器学习与推荐算法
2+阅读 · 2022年8月10日
生成扩散模型漫谈:DDPM = 贝叶斯 + 去噪
PaperWeekly
1+阅读 · 2022年7月24日
从重参数的角度看离散概率分布的构建
PaperWeekly
0+阅读 · 2022年5月28日
从泰勒展开来看梯度下降算法
深度学习每日摘要
13+阅读 · 2019年4月9日
机器学习常见模式LogSumExp解密
论智
21+阅读 · 2018年10月30日
变分自编码器VAE:一步到位的聚类方案
PaperWeekly
25+阅读 · 2018年9月18日
相关基金
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
3+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
1+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2008年12月31日
Top
微信扫码咨询专知VIP会员