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

摘要

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 + 1/k + is an element of)-approximate solution for an arbitrary positive integer k and positive real number is an element of. For graphs with n vertices and m edges, the running time of the local search algorithm is O(b(k+1) (Delta - 1)(k)nm is an element of(-1)) where Delta 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) 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(b(k+1) (Delta - 1)(k-1)m log 1/is an element of) time and obtains a (1/(2 + 1/k) - is an element of)-approximate solution. (C) 2016 Elsevier B.V. All rights reserved.