Abstract: Submodular optimization is widely used in large datasets. In order to speed up the problems solving, it is essential to design low-adaptive algorithms to achieve acceleration in parallel. In general, the function values are given by a value oracle, but in practice, the oracle queries may consume a lot of time. Hence, how to strike a balance between optimizing them is important. In this paper, we focus on maximizing a normalized and strictly monotone set function with the diminishing-return ratio γ under a cardinality constraint, and propose two algorithms to deal with it. We apply the adaptive sequencing technique to devise the first algorithm, whose approximation ratio is arbitrarily close to 1 - e^-γ in O(log n · log(log k/γ)) adaptive rounds, and requires O(n² ·log(log k/γ)) queries. Then by adding preprocessing and parameter estimation steps to the first algorithm, we get the second one. The second algorithm trades a small sacrifice in adaptive complexity for a significant improvement in query complexity. With the same approximation and adaptive complexity, the query complexity is improved to O(n ·log(log k/γ)). To the best of our knowledge, this is the first paper of designing adaptive algorithms for maximizing a monotone function using the diminishing-return ratio.

Key words: Approximation algorithm, Adaptivity, Nonsubmodular maximization, Cardinality constraint