论文标题
最大化模块化加非单调的下调功能
Maximizing Modular plus Non-monotone Submodular Functions
论文作者
论文摘要
这项工作中的研究问题是放宽非阴性subipular Plus模块化模块，并将整个实际数字域作为其在下闭合集合的家族中的价值范围。我们在给定约束的多层人士中寻找可行的点$ \ mathbf {x}^*$ $ \ mathbf {x}^*\ in \ in \ arg \ max _ {\ mathbf {x} \ in \ mathcal {p} \ subseteq [0,1]^n} f（\ m athbf {x}） $ f $和模块化函数$ \ ell $。我们提供了一种名为\ textsc {测量的具有自适应重量的连续贪婪}的近似算法，该算法可提供保证$ f（\ mathbf {x}）+l（\ mathbf {x}}） f（opt）+\左（\ frac {β-e} { $ opt $是离散问题的最佳积分解决方案。显然，当$β= 0 $时，$ \ ell（opt）$的因子为$ 1 $，这意味着目前负零件完全占主导地位。否则，该因子将不到$ 1/e $ whe $β\ rightarrow \ infty $。我们的工作首先打破了对模块函数的特定值范围的限制，而无需假设非阳性或非阴性作为先前的结果，并量化了具有任意结构的最佳解决方案的近似保证的相对变化。此外，我们还为我们考虑的问题的不Xibibibibibibibibibibibibibity提供了分析。我们表明了一个硬度结果表明，没有多项式算法的输出$ s $满足$ f（s）+\ ell（s）\ geq0.478 \ cdot f（opt）+\ ell（opt）$。
The research problem in this work is the relaxation of maximizing non-negative submodular plus modular with the entire real number domain as its value range over a family of down-closed sets. We seek a feasible point $\mathbf{x}^*$ in the polytope of the given constraint such that $\mathbf{x}^*\in\arg\max_{\mathbf{x}\in\mathcal{P}\subseteq[0,1]^n}F(\mathbf{x})+L(\mathbf{x})$, where $F$, $L$ denote the extensions of the underlying submodular function $f$ and modular function $\ell$. We provide an approximation algorithm named \textsc{Measured Continuous Greedy with Adaptive Weights}, which yields a guarantee $F(\mathbf{x})+L(\mathbf{x})\geq \left(1/e-\mathcal{O}(ε)\right)\cdot f(OPT)+\left(\frac{β-e}{e(β-1)}-\mathcal{O}(ε)\right)\cdot\ell(OPT)$ under the assumption that the ratio of non-negative part within $\ell(OPT)$ to the absolute value of its negative part is demonstrated by a parameter $β\in[0, \infty]$, where $OPT$ is the optimal integral solution for the discrete problem. It is obvious that the factor of $\ell(OPT)$ is $1$ when $β=0$, which means the negative part is completely dominant at this time; otherwise the factor is closed to $1/e$ whe $β\rightarrow\infty$. Our work first breaks the restriction on the specific value range of the modular function without assuming non-positivity or non-negativity as previous results and quantifies the relative variation of the approximation guarantee for optimal solutions with arbitrary structure. Moreover, we also give an analysis for the inapproximability of the problem we consider. We show a hardness result that there exists no polynomial algorithm whose output $S$ satisfies $f(S)+\ell(S)\geq0.478\cdot f(OPT)+\ell(OPT)$.
