  The optimization of submodular functions on the integer lattice has received
much attention recently, but the objective functions of many applications are
non-submodular. We provide two approximation algorithms for maximizing a
non-submodular function on the integer lattice subject to a cardinality
constraint; these are the first algorithms for this purpose that have
polynomial query complexity. We propose a general framework for influence
maximization on the integer lattice that generalizes prior works on this topic,
and we demonstrate the efficiency of our algorithms in this context.
