We consider the problem of minimum cost cover of adaptive-submodular functions, and provide a 4(ln Q+1)-approximation algorithm, where Q is the goal value. This bound is nearly the best possible as the problem does not admit any approximation ratio better than ln Q (unless P=NP). Our result is the first O(ln Q)-approximation algorithm for this problem. Previously, O(ln Q) approximation algorithms were only known assuming either independent items or unit-cost items. Furthermore, our result easily extends to the setting where one wants to simultaneously cover multiple adaptive-submodular functions: we obtain the first approximation algorithm for this generalization.
翻译:我们考虑了适应性子模块功能的最低成本覆盖问题,并提供了一种4 (ln Q1)- 接近算法,其中Q是目标值。这几乎是最好的,因为问题并不比Q(除非P=NP)中的任何近似比率好。我们的结果是这一问题的第一个O(ln Q)-接近性算法。以前,O(ln Q)近似算法只假定独立项目或单位成本项目。此外,我们的结果很容易延伸到人们希望同时覆盖多个适应性子模块功能的场合:我们获得了这种概括化的第一个近似算法。