Adaptive Submodular Ranking and Routing

• 成果类型: Article
• 署名作者: Navidi, Fatemeh; Kambadur, Prabhanjan; Nagarajan, Viswanath
• 署名单位: University of Michigan System; University of Michigan; Bloomberg L.P.
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2019.1889
• 发表日期: 2020
• 页码: 856-877
• 关键词: submodularity; stochastic optimization; Approximation algorithms

摘要

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.