- Authors:
-
-
Gørtz, Inge Li
;
Close
0000-0002-8322-4952
Department of Informatics and Mathematical Modeling, Technical University of Denmark - Nagarajan, Viswanath ;
- Saket, Rishi
-
Gørtz, Inge Li
;
- Editor:
- Czumaj, Artur, Mehlhorn, Kurt, Pitts, Andrew, Wattenhofer, Roger
- DOI:
- 10.1007/978-3-642-31594-7_35
- Abstract:
- We study the classic Vehicle Routing Problem in the setting of stochastic optimization with recourse. StochVRP is a two-stage 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 λ. We present an O(log2n ·log(nλ))-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 ω(1) hardness of approximation for StochVRP, even on star-like metrics on which our algorithm achieves a logarithmic approximation.
- ISBN:
- 9783642315930
- Type:
- Conference paper
- Language:
- English
- Published in:
- Lecture Notes in Computer Science: 39th International Colloquium, Icalp 2012, 2012, p. 411-423
- Main Research Area:
- Science/technology
- Series:
- Lecture Notes in Computer Science
- Conference:
- Automata, Languages, and Programming. 39th International Colloquium, ICALP 2012
- Publisher:
- Springer
- Submission year:
- 2012
- ID:
- 2288131435
Checking for on-site access...
