Invited Session Tue.3.MA 376

Tuesday, 15:15 - 16:45 h, Room: MA 376

Cluster 22: Stochastic optimization [...]

Approximation algorithms for stochastic combinatorial optimization


Chair: Chaitanya Swamy



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

Inge Li 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.



Tuesday, 15:45 - 16:10 h, Room: MA 376, Talk 2

Ramamoorthi Ravi
Approximation algorithms for correlated knapsacks and non-martingale bandits

Coauthors: Anupam Gupta, Ravishankar Krishnaswamy, Marco Molinaro


We give constant-factor approximation algorithms for the stochastic knapsack problem with correlations and cancelations, and also for some budgeted learning problems where the martingale condition is not satisfied, using similar ideas. Indeed, we can show that previously proposed linear programming relaxations for these problems have large integrality gaps. We propose new time-indexed LP relaxations; using a decomposition and "shifting'' approach, we convert these fractional solutions to distributions over strategies, and then use the LP values and the time ordering information from these strategies to devise a randomized scheduling algorithm. We hope our LP formulation and decomposition methods may provide a new way to address other correlated bandit problems with more general contexts.
The paper is available at,



Tuesday, 16:15 - 16:40 h, Room: MA 376, Talk 3

Gwen Spencer
Fragmenting and vaccinating graphs over time and subject to uncertainty: Developing techniques for wildfire and invasive species containment

Coauthor: David Shmoys


Decisions about the containment of harmful processes that spread across landscapes (for example, wildfire and invasive species) often must be made under uncertainty and as the system evolves in time. Not all resources are available immediately and containment efforts may fail to prevent spread. The valuable probabilistic predictions produced by ecologists and foresters have been under-utilized because of the difficulty of optimizing when stochastic features and spatial connectedness (or, in this case, disconnectedness) interact.

I will introduce several simple models in graphs that generalize existing work in the CS theory literature and explain provably-good algorithmic results for several settings. These models capture qualitative tradeoffs with important implications for sustainable management. How should resources for wildfire containment be divided across preventive fuel removals and real-time fire suppression efforts, and how can these deployments be coordinated to maximum advantage? If attempts to block invasive species spread are not perfectly reliable, but redundancy is costly, where should managers concentrate their resources?


  There are three major facts that should be watched out for in all payday loans in the United States. Since its introduction in the market buying Order Cialis can be exclusively in pharmacy chains with a prescription from a doctor. I agree that this is very inconvenient and takes a lot of time and effort.