Computer Science – Data Structures and Algorithms
Scientific paper
2012-02-26
Computer Science
Data Structures and Algorithms
20 Pages, 1 figure Revision corrects the statement and proof of Theorem 1.2
Scientific paper
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 two routes: fixed and recourse. The fixed route is computed using only a demand distribution. Then after observing the demand instantiations, a recourse route is computed -- but costs here become more expensive by a factor lambda. We present an O(log^2 n log(n lambda))-approximation algorithm for this stochastic routing problem, under arbitrary distributions. The main idea in this result is relating StochVRP to a special case of submodular orienteering, called knapsack rank-function orienteering. We also give a better approximation ratio for knapsack rank-function orienteering than what follows from prior work. Finally, we provide a Unique Games Conjecture based omega(1) hardness of approximation for StochVRP, even on star-like metrics on which our algorithm achieves a logarithmic approximation.
Goertz Inge Li
Nagarajan Viswanath
Saket Rishi
No associations
LandOfFree
Stochastic Vehicle Routing with Recourse does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Stochastic Vehicle Routing with Recourse, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Stochastic Vehicle Routing with Recourse will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-261844