Resolving the Approximability of Offline and Online Non-monotone DR-Submodular Maximization over General Convex Sets
Resolving the Approximability of Offline and Online Non-monotone DR-Submodular Maximization over General Convex Sets
复制标题
DOI：
10.48550/arxiv.2210.05965
复制
发表时间：
2022-10
期刊：
影响因子：
--
通讯作者：
Loay Mualem;Moran Feldman
中科院分区：
文献类型：
--
作者：
Loay Mualem;Moran Feldman
近年来，DR子模连续函数的最大化成为一个重要的研究领域，在机器学习、通信系统、运筹学和经济学领域有许多实际应用。由于 Vondr'ak (2013) 的不可逼近性结果，该领域的大多数工作都研究了受下闭凸集约束影响的最大化。然而，杜尔等人。 （2021）表明，可以通过证明近似比率来绕过这种不可近似性，该近似比率是 $m$ 的函数，$m$ 是任何可行向量的最小 $\ell_{\infty}$ 范数。鉴于这一观察，有可能获得在一般凸集约束下最大化 DR 子模函数的结果，这导致了针对该问题的多项工作。其中最新的是 Du (2022) 提出的多项式时间 $\tfrac{1}{4}(1 - m)$ 近似离线算法。然而，对于相应的在线问题，仅已知次指数时间 $\tfrac{1}{3\sqrt{3}}(1 - m)$ 近似算法。在这项工作中，我们提出了一种多项式时间在线算法，与最先进的离线算法的 $\tfrac{1}{4}(1 - m)$ 近似相匹配。我们还提出了一个不可近似性结果，表明我们的在线算法和 Du（2022）离线算法在强意义上都是最优的。最后，我们研究了我们的算法和 Du 算法（之前仅在理论上研究过）的实证性能，并表明它们在收入最大化、位置汇总和二次规划应用方面始终优于之前建议的算法。
In recent years, maximization of DR-submodular continuous functions became an important research field, with many real-worlds applications in the domains of machine learning, communication systems, operation research and economics. Most of the works in this field study maximization subject to down-closed convex set constraints due to an inapproximability result by Vondr\'ak (2013). However, Durr et al. (2021) showed that one can bypass this inapproximability by proving approximation ratios that are functions of $m$, the minimum $\ell_{\infty}$-norm of any feasible vector. Given this observation, it is possible to get results for maximizing a DR-submodular function subject to general convex set constraints, which has led to multiple works on this problem. The most recent of which is a polynomial time $\tfrac{1}{4}(1 - m)$-approximation offline algorithm due to Du (2022). However, only a sub-exponential time $\tfrac{1}{3\sqrt{3}}(1 - m)$-approximation algorithm is known for the corresponding online problem. In this work, we present a polynomial time online algorithm matching the $\tfrac{1}{4}(1 - m)$-approximation of the state-of-the-art offline algorithm. We also present an inapproximability result showing that our online algorithm and Du's (2022) offline algorithm are both optimal in a strong sense. Finally, we study the empirical performance of our algorithm and the algorithm of Du (which was only theoretically studied previously), and show that they consistently outperform previously suggested algorithms on revenue maximization, location summarization and quadratic programming applications.