BEGIN:VCALENDAR
PRODID:-//Mercury//HGEvent//EN
VERSION:2.0
METHOD:PUBLISH
BEGIN:VEVENT
STATUS:CONFIRMED
LAST-MODIFIED:20140204T221522
PRIORITY:0
CLASS:PUBLIC
UID:ATEvent-eed436ece7e23bbcfe0d4623c4969225
SUMMARY:ARC Colloquium: Balasubramanian Sivan\, University of Wisconsin-Madison
DESCRIPTION:Title: Prior Robust Optimization\nAbstract:\nThe focus of this talk is optimization in the presence of uncertain inputs. We model uncertainty as input being drawn from one among a large known class of distributions\, however the specific distribution is unknown to the algorithm. The goal is to develop a single algorithm that for every distribution in this class\, performs approximately as well as the optimal algorithm tailored for that specific distribution. Such algorithms are robust to assumptions on priordistributions and are good candidates for deployment in real systems.\nIn this talk\, we present general techniques for developing prior robust algorithms for two distinct lines of research --- online algorithms and mechanism design. In online algorithms\, we present our results for a very general class of resource allocation problems with several applications\, including to internet advertising. We develop a simple-to-implement prior robust algorithm with near optimal profit guarantee. Our algorithm has been deployed globally along with Microsoft MSN's display ads serving engine. In mechanism design\, we focus on the well studied makespan minimization problem in machine scheduling. Here\, our goal is to schedule jobs with stochastic runtimes on machines which are operated by strategic agents who hold the runtimes private. We design simple-to-implement truthful prior robust mechanisms that under different distributional assumptions provide constant and sub-logarithmic approximations to expected makespan.\n \n
DTSTART:20130204T130000
DTEND:20130204T130000
CREATED:20130201T101504
DTSTAMP:20130201T101504
SEQUENCE:0
LOCATION:
END:VEVENT
END:VCALENDAR