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


Alan Kuhnle, J. David Smith, Victoria G.Crawford, My T. Thai ;
Proceedings of the 35th International Conference on Machine Learning, PMLR 80:2791-2800, 2018.


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.

Related Material