Mathematics Colloquium
Rakesh Vohra
University of Pennsylvania
Title: Linear Programming and Prophet Inequalities
Date: Thursday March 5th
Place and Time: Room 201, Love Building, 3:35-4:25
Abstract. Prophet inequalities bound the expected reward that can be obtained in a class of stopping problems by the optimal reward of the corresponding off-line problem. We use linear programming techniques to obtain prophet inequalities for a class of stopping problems associated with selecting a point in a polyhedron. One application is to `computational sprinting’, in which a chip temporarily exceeds its sustainable thermal power budget to provide instantaneous throughput, after which the chip must return to nominal operation to cool down. We also illustrate the usefulness of the approach by giving some new and simple derivations of existing results. This is based on joint work with Markos Epitropu.