Wednesday, November 2, 2016 - 4:30pm
Event Calendar Category
LIDS & Stats Tea
Speaker Name
Will Ma
Affiliation
ORC
Building and Room Number
LIDS Lounge
Abstract
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)