117 citations · 273 across the 35 of their papers we have counts for
3 papers · 1 filter
Approximation Algorithms for Stochastic k-TSP
Alina Ene, Viswanath Nagarajan, Rishi Saket
We consider the stochastic -TSP problem where rewards at vertices are random and the objective is to minimize the expected length of a tour that collects reward . We present…
Adaptivity Gaps for Stochastic Probing: Submodular and XOS Functions
Anupam Gupta, Viswanath Nagarajan, Sahil Singla
Suppose we are given a submodular function over a set of elements, and we want to maximize its value subject to certain constraints. Good approximation algorithms are known for…
Adaptive Submodular Ranking and Routing
Fatemeh Navidi, Prabhanjan Kambadur, Viswanath Nagarajan
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 distributi…