J. David Smith

Fast Maximization of Non-Submodular, Monotonic Functions on the Integer Lattice

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…