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

Alan Kuhnle, J. David Smith, Victoria Crawford, My Thai
Proceedings of the 35th International Conference on Machine Learning, PMLR 80:2786-2795, 2018.

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 this Paper

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.} }
Endnote
%0 Conference Paper %T Fast Maximization of Non-Submodular, Monotonic Functions on the Integer Lattice %A Alan Kuhnle %A J. David Smith %A Victoria Crawford %A My Thai %B Proceedings of the 35th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2018 %E Jennifer Dy %E Andreas Krause %F pmlr-v80-kuhnle18a %I PMLR %P 2786--2795 %U https://proceedings.mlr.press/v80/kuhnle18a.html %V 80 %X 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.
APA
Kuhnle, A., Smith, J.D., Crawford, V. & Thai, M.. (2018). Fast Maximization of Non-Submodular, Monotonic Functions on the Integer Lattice. Proceedings of the 35th International Conference on Machine Learning, in Proceedings of Machine Learning Research 80:2786-2795 Available from https://proceedings.mlr.press/v80/kuhnle18a.html.

Related Material