A Fast Algorithm for Submodular Maximization with a Matroid Constraint

We present a fast algorithm for maximizing monotone submodular function over a matroid constraint. It is a \((1-1/e-\epsilon )\) approximation algorithm with nearly-linear time complexity, where \(\epsilon >0\) . We improve the complexity of the LazySamplingGreedy algorithm proposed by Ene and Nguyen [11], which is the first nearly-linear time algorithm with the same guarantee above. It made \(O(n\ln n\ln (r/\epsilon )/\epsilon )\) calls to the value oracle so that the approximation guarantee above can be obtained with a probability of at least 2/3, where n is the cardinality of the given ground set and r is the rank of the matroid constraint. We improve the complexity and propose the FastLazySamplingGreedy algorithm, which can produce the same approximation ratio with a probability of at least 3/4 and only made \(O((r\ln n+n)\ln (r/\epsilon )/\epsilon )\) calls to the value oracle.