117 citations · 273 across the 35 of their papers we have counts for
6 papers · 2 filters
Capacitated Vehicle Routing with Non-Uniform Speeds
Inge Li Gortz, Marco Molinaro, Viswanath Nagarajan +1
The capacitated vehicle routing problem (CVRP) involves distributing (identical) items from a depot to a set of demand locations, using a single capacitated vehicle. We study a gen…
Robust and MaxMin Optimization under Matroid and Knapsack Uncertainty Sets
Anupam Gupta, Viswanath Nagarajan, R. Ravi
Consider the following problem: given a set system (U,I) and an edge-weighted graph G = (U, E) on the same universe U, find the set A in I such that the Steiner tree cost with term…
When LP is the Cure for Your Matching Woes: Improved Bounds for Stochastic Matchings
Nikhil Bansal, Anupam Gupta, Jian Li +3
Consider a random graph model where each possible edge is present independently with some probability . Given these probabilities, we want to build a large/heavy matching…
On Generalizations of Network Design Problems with Degree Bounds
Nikhil Bansal, Rohit Khandekar, Jochen Konemann +2
Iterative rounding and relaxation have arguably become the method of choice in dealing with unconstrained and constrained network design problems. In this paper we extend the scope…
Approximation Algorithms for Optimal Decision Trees and Adaptive TSP Problems
Anupam Gupta, Viswanath Nagarajan, R. Ravi
We consider the problem of constructing optimal decision trees: given a collection of tests which can disambiguate between a set of possible diseases, each test having a cost,…
When LP is the Cure for Your Matching Woes: Approximating Stochastic Matchings
Nikhil Bansal, Anupam Gupta, Viswanath Nagarajan +1
This results in this paper have been merged with the result in arXiv:1002.3763v1 The authors would like to withdraw this version. Please see arXiv:1008.5356v1 for the merged versio…