The greedy algorithm for Submodular Cost Submodular Cover is shown to achieve new bicriteria approximation ratios when the benefit function is only accessible through an ϵ-approximate oracle, provided the smallest marginal gain exceeds a threshold.
Fast Maximization of Non-Submodular, Monotonic Functions on the Integer Lattice
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
abstract
The optimization of submodular functions on the integer lattice has received much attention recently, but the objective functions of many applications are non-submodular. We provide two approximation algorithms for maximizing a non-submodular function on the integer lattice subject to a cardinality constraint; these are the first algorithms for this purpose that have polynomial query complexity. We propose a general framework for influence maximization on the integer lattice that generalizes prior works on this topic, and we demonstrate the efficiency of our algorithms in this context.
fields
cs.DS 1years
2019 1verdicts
CONDITIONAL 1representative citing papers
citing papers explorer
-
Submodular Cost Submodular Cover with an Approximate Oracle
The greedy algorithm for Submodular Cost Submodular Cover is shown to achieve new bicriteria approximation ratios when the benefit function is only accessible through an ϵ-approximate oracle, provided the smallest marginal gain exceeds a threshold.