Adaptive Submodular Ranking and Routing
  We study a general stochastic ranking problem where an algorithm needs to
adaptively select a sequence of elements so as to "cover" a random scenario
(drawn from a known distribution) at minimum expected cost. The coverage of
each scenario is captured by an individual submodular function, where the
scenario is said to be covered when its function value goes above a given
threshold. We obtain a logarithmic factor approximation algorithm for this
adaptive ranking problem, which is the best possible (unless P=NP). This
problem unifies and generalizes many previously studied problems with
applications in search ranking and active learning. The approximation ratio of
our algorithm either matches or improves the best result known in each of these
special cases. Furthermore, we extend our results to an adaptive vehicle
routing problem, where costs are determined by an underlying metric. This
routing problem is a significant generalization of the previously-studied
adaptive traveling salesman and traveling repairman problems. Our approximation
ratio nearly matches the best bound known for these special cases. Finally, we
present experimental results for some applications of adaptive ranking.
