A (k+3)/2-approximation algorithm for monotone submodular k-set packing and general k-exchange systems

Justin Ward
We consider the monotone submodular k-set packing problem in the context of the more general problem of maximizing a monotone submodular function in a k-exchange system. These systems, introduced by Feldman et al. [Feldman,2011], generalize the matroid k-parity problem in a wide class of matroids and capture many other combinatorial optimization problems. We give a deterministic, non-oblivious local search algorithm that attains an approximation ratio of (k + 3)/2 + epsilon for the problem of...