Unconstrained Submodular Maximization with Constant Adaptive Complexity
L. Chen, M. Feldman, and A. Karbasi. (2018)cite arxiv:1811.06603Comment: Authors are listed in alphabetical order.
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 $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.
Description
[1811.06603] Unconstrained Submodular Maximization with Constant Adaptive Complexity
%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
}