Will Ma, Columbia University

Abstract

Randomized rounding is a technique that was originally used to approximate hard offline discrete optimization problems from a mathematical programming relaxation. Since then it has also been used to approximately solve sequential stochastic optimization problems, overcoming the curse of dimensionality. To elaborate, one first writes a tractable linear programming relaxation that prescribes probabilities with which actions should be taken. Rounding then designs a (randomized) online policy that approximately preserves all of these probabilities, with the challenge being that the online policy faces hard constraints, whereas the prescribed probabilities only have to satisfy these constraints in expectation. Moreover, unlike classical randomized rounding for offline problems, the online policy's actions unfold sequentially over time, interspersed by uncontrollable stochastic realizations that affect the feasibility of future actions.

We provide an introduction for using randomized rounding to design online policies, through three self-contained examples representing fundamental problems in the area: online contention resolution, stochastic probing, and stochastic knapsack, based on the first three sections of this tutorial: https://arxiv.org/pdf/2407.20419

See: https://theory.cs.rutgers.edu/theory_seminar