Fast Maximization of Non-Submodular, Monotonic Functions on the Integer Lattice
Abstract
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.
Cite
Text
Kuhnle et al. "Fast Maximization of Non-Submodular, Monotonic Functions on the Integer Lattice." International Conference on Machine Learning, 2018.Markdown
[Kuhnle et al. "Fast Maximization of Non-Submodular, Monotonic Functions on the Integer Lattice." International Conference on Machine Learning, 2018.](https://mlanthology.org/icml/2018/kuhnle2018icml-fast/)BibTeX
@inproceedings{kuhnle2018icml-fast,
title = {{Fast Maximization of Non-Submodular, Monotonic Functions on the Integer Lattice}},
author = {Kuhnle, Alan and Smith, J. David and Crawford, Victoria and Thai, My},
booktitle = {International Conference on Machine Learning},
year = {2018},
pages = {2786-2795},
volume = {80},
url = {https://mlanthology.org/icml/2018/kuhnle2018icml-fast/}
}