Wednesday, November 2, 2016 - 4:30pm
Event Calendar Category
LIDS & Stats Tea
Building and Room Number
We consider two stochastic optimization algorithms which make adaptive decisions over time as information is revealed, except instead of making decisions based on the realized current state, they consider the distribution of all possible current states, given the past decisions of the algorithm (and any online information observed thus far). This idea helps the first algorithm achieves a tight 1/2-approximation algorithm for the Correlated Stochastic Knapsack problem. This idea helps the second algorithm achieve a 1/4-competitive ratio for Online Edge-Weighted Matching with Stochastic Rewards.
(second algorithm is joint work with Xi Chen, David Simchi-Levi, and Linwei Xin)