  We study the problem of maximizing a submodular function, subject to a
cardinality constraint, with a set of agents communicating over a connected
graph. We propose a distributed greedy algorithm that allows all the agents to
converge to a near-optimal solution to the global maximization problem using
only local information and communication with neighbors in the graph. The
near-optimal solution approaches the (1-1/e) approximation of the optimal
solution to the global maximization problem with an additive factor that
depends on the number of communication steps in the algorithm. We then analyze
convergence guarantees of the proposed algorithm. This analysis reveals a
tradeoff between the number of communication steps and the performance of the
algorithm. Finally, we extend our analysis to nonsubmodular settings, using the
notion of approximate submodularity.
