21 citations · 47 across the 19 of their papers we have counts for
4 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…
On the Approximability of Digraph Ordering
Sreyash Kenkre, Vinayaka Pandit, Manish Purohit +1
Given an n-vertex digraph D = (V, A) the Max-k-Ordering problem is to compute a labeling maximizing the number of forward edges, i.e. edges (u,v) such that $\ell…
A PTAS for the Classical Ising Spin Glass Problem on the Chimera Graph Structure
Rishi Saket
We present a polynomial time approximation scheme (PTAS) for the minimum value of the classical Ising Hamiltonian with linear terms on the Chimera graph structure as defined in the…
Stochastic Vehicle Routing with Recourse
Inge Li Goertz, Viswanath Nagarajan, Rishi Saket
We study the classic Vehicle Routing Problem in the setting of stochastic optimization with recourse. StochVRP is a two-stage optimization problem, where demand is satisfied using…