版权所有:内蒙古大学图书馆 技术提供:维普资讯• 智图
内蒙古自治区呼和浩特市赛罕区大学西街235号 邮编: 010021
作者机构:School of Mathematical Sciences University of Chinese Academy of Sciences Beijing100049 China College of Sciecne Tianjin University of Technology Tianjin300072 China Beijing Institute for Scientific and Engineering Computing Beijing University of Technology Beijing100124 China School of Mathematics and Statistics Shandong Normal University Jinan250014 China Department of Computer Science University of Texas at Dallas RichardsonTX75080 United States
出 版 物:《SSRN》
年 卷 期:2024年
核心收录:
摘 要:In this paper, we investigate regularized non-monotone submodular maximization over a down-monotone family of sets by applying the Lyapunov method and the distorted continuous greedy algorithm. Based on the Lyapunov method, we systematically design parameterized algorithm frameworks in two phases. In the first phase, a theoretical approximation algorithm can be derived, as long as a set of parameters is chosen. Contingent upon the selection of a suitable set of parameters, the approximation guarantee can achieve $(1/e, \frac{\gamma-\gamma/e-1}{\gamma-1})$, where $\gamma\in[0,1)\cup[e,+\infty)$ reflects the relative dominance of the positive and negative parts of the optimal value for the regular term. In the second phase, an implementable algorithm is presented through discretization in $\mathcal{O}(n^3/\epsilon)$ with arbitrarily small loss in guarantee. Additionally, we establish that no polynomial-time algorithm yields a $(0.478,\lambda)$-approximation with $\lambda\in[0,1]$. Furthermore, we demonstrate that the Lyapunov method can also be applied in regularized monotone submodular maximization with the tight $(1-1/e, 1)$-approximation ratio. © 2024, The Authors. All rights reserved.