Beyond Pointwise Submodularity: Non-Monotone Adaptive Submodular
  Maximization in Linear Time
  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. We also generalize
our study by considering a partition matroid constraint, and develop a
linear-time algorithm for monotone and fully adaptive submodular functions.
