Adaptive Submodular Ranking and Routing

Many applications of stochastic optimization involve making sequential decisions until some stopping criterion is satisfied. For example, in medical diagnosis, a doctor needs to perform an adaptive sequence of tests on a patient in order to diagnose a disease. Being adaptive allows the doctor to choose the next test based on the outcomes of prior tests. Given an a priori probability distribution over diseases, the goal is to minimize the expected cost of tests. In “Adaptive Submodular Ranking and Routing,” Navidi, Kambadur, and Nagarajan formulate a general stochastic optimization problem in which the stopping criterion corresponds to covering a submodular function. Such problems arise in many applications, including active learning, robotics, and disaster management. The authors obtain efficient algorithms with best possible performance guarantees. These results also extend to a vehicle-routing setting, in which one needs to plan an adaptive route based on information observed at nodes in the network. The authors also present experimental results on a data set arising in the identification of toxic chemicals, thereby demonstrating the practical applicability of their algorithm.