Invited Session Mon.3.MA 144

Monday, 15:15 - 16:45 h, Room: MA 144

Cluster 22: Stochastic optimization [...]

Approximation algorithms for stochastic revenue management optimization


Chair: Retsef Levi



Monday, 15:15 - 15:40 h, Room: MA 144, Talk 1

Retsef Levi
Near-optimal algorithms for assortment planning under dynamic substitution and stochastic demand

Coauthors: Vineet Goyal, Danny Segev


We consider a single-period assortment planning problem under a dynamic-substitution model with stochastic demand and give a polynomial time approximation scheme for the problem under fairly general assumptions. Our algorithm computes an assortment containing only a small number of product types and obtains near-optimal revenue. We also present several complexity results for the problem that indicate that our assumptions are almost 'necessary' to solve it efficiently.



Monday, 15:45 - 16:10 h, Room: MA 144, Talk 2

Dragos Florin Ciocan
Dynamic allocation problems with volatile demand

Coauthor: Vivek Farias


We present a simple, easy to interpret algorithm for a large class of dynamic allocation problems with unknown, volatile demand. Potential applications include Ad Display problems and network revenue management problems. The algorithm operates in an online fashion and relies on re-optimization and forecast updates. The algorithm is robust (as witnessed by uniform worst case guarantees for arbitrarily volatile demand) and in the event that demand volatility (or equivalently deviations in realized demand from forecasts) is not large, the method is simultaneously optimal. Computational experiments, including experiments with data from real world problem instances, demonstrate the practicality and value of the approach. From a theoretical perspective, we introduce a new device – a balancing property – that allows us to understand the impact of changing bases in our scheme.



Monday, 16:15 - 16:40 h, Room: MA 144, Talk 3

Cong Shi
Revenue management of reusable resources with advanced reservations

Coauthor: Retsef Levi


This paper studies a class of revenue management problems in systems with reusable resources and advanced reservations. A simple control policy called the class selection policy (CSP) is proposed based on solving a knapsack-type linear program (LP). It is shown that the CSP and its variants perform provably near-optimal under several classical asymptotic parameter regimes, such as the critically loaded and the Halfin-Whitt heavy-traffic regimes. The analysis is based on entirely new approaches that model the problem as loss network systems with advanced reservations. In particular, asymptotic upper bounds on the blocking probabilities are derived under the above mentioned heavy-traffic regimes. There have been very few results on loss network systems with advanced reservations, and we believe that the approaches developed in this paper will be applicable in other operations management and other applications domains.


  California Payday Loans. But it is worth noting that these tests were carried out on the blood cells. Therefore, it's too early to say about scientific evidence of Viagra influence on blood clots.