Faster approximation algorithms for maximizing a monotone submodular function subject to a b-matching constraint

•Two algorithms for maximizing a monotone submodular function under a constraint.•One is a 1/4-approximation algorithm that is faster than the greedy algorithm.•The other is a faster variant of the local search algorithm.

Maximizing a monotone submodular function subject to a b-matching constraint is increasing in importance due to its application to the content spread maximization problem, but few practical algorithms are known other than the greedy algorithm. The best approximation scheme so far is the local search algorithm, proposed by Feldman, Naor, Schwartz, and Ward [8] (2011). It obtains a 1/(2+1k+ϵ)-approximate solution for an arbitrary positive integer k and positive real number ϵ. For graphs with n vertices and m   edges, the running time of the local search algorithm is O(bk+1(Δ−1)knmϵ−1)O(bk+1(Δ−1)knmϵ−1) where Δ is the maximum degree, which is impractical for large problems. In this paper, we present two new algorithms for this problem. One is a find walk algorithm that runs in O(bm)O(bm) time and achieves 1/4-approximation. It is faster than the greedy algorithm whose approximation ratio is 1/3. The other one is a randomized local search algorithm that is a faster variant of the local search algorithm. In expectation, it runs in O(bk+1(Δ−1)k−1mlog⁡1ϵ) time and obtains a (1/(2+1k)−ϵ)-approximate solution.