Adaptive Submodular Ranking and Routing

• Published in: Operations research 2020-05, Vol.68 (3), p.856-877
• Main Authors: Navidi, Fatemeh, Kambadur, Prabhanjan, Nagarajan, Viswanath
• Format: Article
• Language: English
• Subjects: Adaptive algorithms; Algorithms; analysis of algorithms: suboptimal algorithms; Approximation; approximation algorithms; Machine learning; Mathematical analysis; networks/graphs: stochastic; Operations research; Optimization; Ranking; Ratings & rankings; Route planning; stochastic optimization; submodularity
• ISSN: 0030-364X; 1526-5463
• DOI: 10.1287/opre.2019.1889

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. We study a general stochastic ranking problem in which 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, in which 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, in which 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.