ICML 2018oral72 citations
Fast Maximization of Non-Submodular, Monotonic Functions on the Integer Lattice
Alan Kuhnle, J. David Smith, Victoria Crawford, My Thai
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.
BibTeX
@InProceedings{pmlr-v80-kuhnle18a,
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 = {Proceedings of the 35th International Conference on Machine Learning},
pages = {2786--2795},
year = {2018},
editor = {Dy, Jennifer and Krause, Andreas},
volume = {80},
series = {Proceedings of Machine Learning Research},
month = {10--15 Jul},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v80/kuhnle18a/kuhnle18a.pdf},
url = {https://proceedings.mlr.press/v80/kuhnle18a.html},
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.}
}