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

05/17/2018
by   Alan Kuhnle, et al.
0

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.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset