Optimal Algorithms for Continuous Non-monotone Submodular and DR-Submodular Maximization
Rad Niazadeh, Tim Roughgarden, Joshua Wang
Abstract
In this paper we study the fundamental problems of maximizing a continuous non monotone submodular function over a hypercube, with and without coordinate-wise concavity. This family of optimization problems has several applications in machine learning, economics, and communication systems. Our main result is the first 1/2 approximation algorithm for continuous submodular function maximization; this approximation factor of is the best possible for algorithms that use only polynomially many queries. For the special case of DR-submodular maximization, we provide a faster 1/2-approximation algorithm that runs in (almost) linear time. Both of these results improve upon prior work [Bian et al., 2017, Soma and Yoshida, 2017, Buchbinder et al., 2012].
BibTeX
@inproceedings{NEURIPS2018_cdfa4c42,
author = {Niazadeh, Rad and Roughgarden, Tim and Wang, Joshua},
booktitle = {Advances in Neural Information Processing Systems},
editor = {S. Bengio and H. Wallach and H. Larochelle and K. Grauman and N. Cesa-Bianchi and R. Garnett},
pages = {},
publisher = {Curran Associates, Inc.},
title = {Optimal Algorithms for Continuous Non-monotone Submodular and DR-Submodular Maximization},
url = {https://proceedings.neurips.cc/paper_files/paper/2018/file/cdfa4c42f465a5a66871587c69fcfa34-Paper.pdf},
volume = {31},
year = {2018}
}