论文标题
统一的贪婪的近似性超出了次管的最大化
Unified greedy approximability beyond submodular maximization
论文作者
论文摘要
我们考虑基质性的目标功能类别限制了最大化问题，贪婪算法保证了持续近似。 We propose the new class of $γ$-$α$-augmentable functions and prove that it encompasses several important subclasses, such as functions of bounded submodularity ratio, $α$-augmentable functions, and weighted rank functions of an independence system of bounded rank quotient - as well as additional objective functions for which the greedy algorithm yields an approximation. For this general class of functions, we show a tight bound of $\fracαγ\cdot\frac{\mathrm{e}^α}{\mathrm{e}^α-1}$ on the approximation ratio of the greedy algorithm that tightly interpolates between bounds from the literature for functions of bounded submodularity ratio and for $α$-augmentable功能。作为副产品的派贴，我们通过在所有$α\ geq1 $中获得了$α$ - 授权功能的紧密下限，以缩小[Math.prog。，2020]中留下的间隙。对于独立系统的加权等级函数，我们的紧密界限变成$ \fracαγ$，该$ \fracαγ$恢复了$ 1/q $的$ 1/q $的独立性系统，至少$ q $。
We consider classes of objective functions of cardinality constrained maximization problems for which the greedy algorithm guarantees a constant approximation. We propose the new class of $γ$-$α$-augmentable functions and prove that it encompasses several important subclasses, such as functions of bounded submodularity ratio, $α$-augmentable functions, and weighted rank functions of an independence system of bounded rank quotient - as well as additional objective functions for which the greedy algorithm yields an approximation. For this general class of functions, we show a tight bound of $\fracαγ\cdot\frac{\mathrm{e}^α}{\mathrm{e}^α-1}$ on the approximation ratio of the greedy algorithm that tightly interpolates between bounds from the literature for functions of bounded submodularity ratio and for $α$-augmentable functions. In paritcular, as a by-product, we close a gap left in [Math.Prog., 2020] by obtaining a tight lower bound for $α$-augmentable functions for all $α\geq1$. For weighted rank functions of independence systems, our tight bound becomes $\fracαγ$, which recovers the known bound of $1/q$ for independence systems of rank quotient at least $q$.
