Loading Events

« All Events

  • This event has passed.

Eindhoven Stochastic Seminar

May 18, 2021, 15:45 - 16:45

Shaojie Tang (UTD)

Fast Adaptive Submodular Maximization

In this paper, we study the non-monotone adaptive submodular maximization problem subject to a cardinality constraint.  We first revisit the  adaptive random greedy algorithm  proposed in \citep{gotovos2015non}, where they show that this algorithm achieves a $1/e$ approximation ratio if the objective function is adaptive submodular and pointwise submodular. It is not clear whether the same guarantee holds under adaptive submodularity (without resorting to pointwise submodularity) or not. Our first contribution is to show that the adaptive random greedy algorithm achieves a $1/e$ approximation ratio under  adaptive submodularity.  One limitation of the adaptive random greedy algorithm is that it requires $O(n\times k)$ value oracle queries, where $n$ is the size of the ground set and $k$ is the cardinality constraint. Our second contribution is to develop the first linear-time algorithm for the non-monotone adaptive submodular maximization problem. Our algorithm achieves a  $1/e-\epsilon$ approximation ratio (this bound is improved to $1-1/e-\epsilon$ for monotone case), using only $O(n\epsilon^{-2}\log \epsilon^{-1})$ value oracle queries.    Notably, $O(n\epsilon^{-2}\log \epsilon^{-1})$ is independent of the cardinality constraint.  For the monotone case, we propose a faster algorithm that achieves a $1-1/e-\epsilon$ approximation ratio in expectation  with $O(n \log  \frac{1}{\epsilon})$ value oracle queries.

Details

Date:
May 18, 2021
Time:
15:45 - 16:45

Venue

MS Teams

Comments are closed.