Online Covering: Secretaries, Prophets and Universal Maps

Explore a Google TechTalk presented by Roie Levin on online covering algorithms for integer programs (IPs) with applications to secretary and prophet problems. Delve into a polynomial-time algorithm achieving an O(log mn) competitive ratio for online covering IPs with randomly ordered constraints, matching the best offline bound and overcoming known lower bounds. Discover how this result extends to the prophet version of the problem and its implications for building universal maps with limited samples. Learn about the speaker's background in algorithms for uncertain environments and submodular optimization. Gain insights into cutting-edge research in algorithms, combinatorics, and optimization presented at this Google Research Algorithm Seminar.

Online Covering: Secretaries, Prophets and Universal Maps