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的变式,其适应性复杂性比文献中任何先前的算法的更小。第二个部分是可平行的门槛程序,用于添加超过一个固定阈值的要素。最后,我们在前六轮的适应性分析中展示了我们以往的、客观的亚定级分析结果。