Ignoring Reality to Improve Approximation / Competitive Ratios in Expectation

Wednesday, November 2, 2016 - 4:30pm

Event Calendar Category

LIDS & Stats Tea

Speaker Name

Will Ma



Building and Room Number

LIDS Lounge


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)