%0 Journal Article %1 chen2018unconstrained %A Chen, Lin %A Feldman, Moran %A Karbasi, Amin %D 2018 %K convex optimization %T Unconstrained Submodular Maximization with Constant Adaptive Complexity %U http://arxiv.org/abs/1811.06603 %X In this paper, we consider the unconstrained submodular maximization problem. We propose the first algorithm for this problem that achieves a tight $(1/2-\varepsilon)$-approximation guarantee using $O(\varepsilon^-1)$ adaptive rounds and a linear number of function evaluations. No previously known algorithm for this problem achieves an approximation ratio better than $1/3$ using less than $Ømega(n)$ rounds of adaptivity, where $n$ is the size of the ground set. Moreover, our algorithm easily extends to the maximization of a non-negative continuous DR-submodular function subject to a box constraint and achieves a tight $(1/2-\varepsilon)$-approximation guarantee for this problem while keeping the same adaptive and query complexities.

@article{chen2018unconstrained, abstract = {In this paper, we consider the unconstrained submodular maximization problem. We propose the first algorithm for this problem that achieves a tight $(1/2-\varepsilon)$-approximation guarantee using $\tilde{O}(\varepsilon^{-1})$ adaptive rounds and a linear number of function evaluations. No previously known algorithm for this problem achieves an approximation ratio better than $1/3$ using less than $\Omega(n)$ rounds of adaptivity, where $n$ is the size of the ground set. Moreover, our algorithm easily extends to the maximization of a non-negative continuous DR-submodular function subject to a box constraint and achieves a tight $(1/2-\varepsilon)$-approximation guarantee for this problem while keeping the same adaptive and query complexities.}, added-at = {2019-06-27T16:11:08.000+0200}, author = {Chen, Lin and Feldman, Moran and Karbasi, Amin}, biburl = {https://www.bibsonomy.org/bibtex/2da891d7e1056a2b333da3262e6feff27/kirk86}, description = {[1811.06603] Unconstrained Submodular Maximization with Constant Adaptive Complexity}, interhash = {9013cc548ccab6033a7805e701a1863f}, intrahash = {da891d7e1056a2b333da3262e6feff27}, keywords = {convex optimization}, note = {cite arxiv:1811.06603Comment: Authors are listed in alphabetical order}, timestamp = {2019-06-27T16:11:08.000+0200}, title = {Unconstrained Submodular Maximization with Constant Adaptive Complexity}, url = {http://arxiv.org/abs/1811.06603}, year = 2018 }