Prophet inequalities and secretary problems have been extensively studied in recent years due to their elegance, connections to online algorithms, stochastic optimization, and mechanism design problems in game theoretic settings. Rubinstein and Singla developed a notion of combinatorial prophet inequalities in order to generalize the standard prophet inequality setting to combinatorial valuation functions such as submodular and subadditive functions. For non-negative submodular functions they demonstrated a constant factor prophet inequality for matroid constraints. Along the way they showed a variant of the correlation gap for non-negative submodular functions. In this paper we revisit their notion of correlation gap as well as the standard notion of correlation gap and prove much tighter and cleaner bounds. Via these bounds and other insights we obtain substantially improved constant factor combinatorial prophet inequalities for both monotone and non-monotone submodular functions over any constraint that admits an Online Contention Resolution Scheme. In addition to improved bounds we describe efficient polynomial-time algorithms that achieve these bounds.


翻译:近几年来,对先知的不平等和秘书问题进行了广泛研究,原因是其优雅、与在线算法的连接、随机优化和游戏理论环境中的机制设计问题。Rubinstein和Singla发展了一个组合先知不平等的概念,目的是将标准的先知不平等环境推广到组合评估功能,如子模块和子添加功能。对于非负的子模块功能,它们表现出了非负的预知对子模块制约的一贯不平等。与此同时,它们展示了非负的子模块功能的关联差距的变式。在本文中,我们重新审视了它们的相关性差距概念以及相关性差距的标准概念,并证明这些界限更加紧凑和清洁。通过这些界限和其他洞见,我们大大改进了单调和亚模块对接受在线内容解析计划的任何制约的常态组合先知不平等。除了改进了界限外,我们还描述了实现这些界限的有效多时算法。

0
下载
关闭预览

相关内容

专知会员服务
56+阅读 · 2021年4月12日
专知会员服务
50+阅读 · 2020年12月14日
【AAAI2021】小样本学习多标签意图检测
专知会员服务
54+阅读 · 2020年12月8日
元自步学习
专知会员服务
33+阅读 · 2020年9月4日
Linux导论,Introduction to Linux,96页ppt
专知会员服务
77+阅读 · 2020年7月26日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
机器学习入门的经验与建议
专知会员服务
92+阅读 · 2019年10月10日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
(TensorFlow)实时语义分割比较研究
机器学习研究会
9+阅读 · 2018年3月12日
计算机视觉近一年进展综述
机器学习研究会
9+阅读 · 2017年11月25日
【学习】(Python)SVM数据分类
机器学习研究会
6+阅读 · 2017年10月15日
【推荐】SVM实例教程
机器学习研究会
17+阅读 · 2017年8月26日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Arxiv
0+阅读 · 2021年9月9日
VIP会员
相关VIP内容
专知会员服务
56+阅读 · 2021年4月12日
专知会员服务
50+阅读 · 2020年12月14日
【AAAI2021】小样本学习多标签意图检测
专知会员服务
54+阅读 · 2020年12月8日
元自步学习
专知会员服务
33+阅读 · 2020年9月4日
Linux导论,Introduction to Linux,96页ppt
专知会员服务
77+阅读 · 2020年7月26日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
机器学习入门的经验与建议
专知会员服务
92+阅读 · 2019年10月10日
相关资讯
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
(TensorFlow)实时语义分割比较研究
机器学习研究会
9+阅读 · 2018年3月12日
计算机视觉近一年进展综述
机器学习研究会
9+阅读 · 2017年11月25日
【学习】(Python)SVM数据分类
机器学习研究会
6+阅读 · 2017年10月15日
【推荐】SVM实例教程
机器学习研究会
17+阅读 · 2017年8月26日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Top
微信扫码咨询专知VIP会员