Tuesday, 15:15 - 15:40 h, Room: MA 376


Inge Goertz
Stochastic vehicle routing with recourse

Coauthors: 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 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(log2 n 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.


Talk 1 of the invited session Tue.3.MA 376
"Approximation algorithms for stochastic combinatorial optimization" [...]
Cluster 22
"Stochastic optimization" [...]


  There are three major facts that should be watched out for in all payday loans in the United States. What can cause long-term use of Viagra? In the network and other sources of information, there is no reliable data on the long-term use of Viagra and its negative effects on the body.