For the problem of maximizing a monotone, submodular function with respect to a cardinality constraint $k$ on a ground set of size $n$, we provide an algorithm that achieves the state-of-the-art in both its empirical performance and its theoretical properties, in terms of adaptive complexity, query complexity, and approximation ratio; that is, it obtains, with high probability, query complexity of $O(n)$ in expectation, adaptivity of $O(\log(n))$, and approximation ratio of nearly $1-1/e$. The main algorithm is assembled from two components which may be of independent interest. The first component of our algorithm, LINEARSEQ, is useful as a preprocessing algorithm to improve the query complexity of many algorithms. Moreover, a variant of LINEARSEQ is shown to have adaptive complexity of $O( \log (n / k) )$ which is smaller than that of any previous algorithm in the literature. The second component is a parallelizable thresholding procedure THRESHOLDSEQ for adding elements with gain above a constant threshold. Finally, we demonstrate that our main algorithm empirically outperforms, in terms of runtime, adaptive rounds, total queries, and objective values, the previous state-of-the-art algorithm FAST in a comprehensive evaluation with six submodular objective functions.


翻译:对于在基点限制方面最大限度地增加单调、亚调调制函数的问题,对于在一组大小为美元美元的基础上最大限度地增加一个单调、小调调制函数的问题,我们提供一种算法,在适应性复杂度、查询复杂度和近似率方面,在实验性表现和理论性能两方面都达到最新水平,即适应性复杂度、查询性复杂度和近似率;也就是说,它极有可能获得美元(n)的查询复杂性、美元(log(n)美元)的适配性、近似率近似1-1美元(e)美元。主要算法来自两个可能具有独立兴趣的构成部分。我们算法的第一部分,即LINEARSEQ,作为一种预处理性算法,对于提高许多算法的查询复杂性很有帮助。此外,LINEARSEQ的变式,其适应性复杂性比文献中任何先前的算法的更小。第二个部分是可平行的门槛程序,用于添加超过一个固定阈值的要素。最后,我们在前六轮的适应性分析中展示了我们以往的、客观的亚定级分析结果。

0
下载
关闭预览

相关内容

【干货书】面向计算科学和工程的Python导论,167页pdf
专知会员服务
41+阅读 · 2021年4月7日
最新《图理论》笔记书,98页pdf
专知会员服务
74+阅读 · 2020年12月27日
专知会员服务
50+阅读 · 2020年12月14日
专知会员服务
52+阅读 · 2020年9月7日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
【推荐】免费书(草稿):数据科学的数学基础
机器学习研究会
20+阅读 · 2017年10月1日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Arxiv
0+阅读 · 2022年1月18日
Arxiv
0+阅读 · 2022年1月15日
VIP会员
相关资讯
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
【推荐】免费书(草稿):数据科学的数学基础
机器学习研究会
20+阅读 · 2017年10月1日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Top
微信扫码咨询专知VIP会员