  We consider the problem of maximizing a monotone submodular function in a
$k$-exchange system. These systems, introduced by Feldman et al., generalize
the matroid k-parity problem in a wide class of matroids and capture many other
combinatorial optimization problems. Feldman et al. show that a simple
non-oblivious local search algorithm attains a $(k + 1)/2$ approximation ratio
for the problem of linear maximization in a $k$-exchange system. Here, we
extend this approach to the case of monotone submodular objective functions. We
give a deterministic, non-oblivious local search algorithm that attains an
approximation ratio of $(k + 3)/2$ for the problem of maximizing a monotone
submodular function in a $k$-exchange system.

Data Structures and Algorithms