ARC Colloquium: Balasubramanian Sivan, University of Wisconsin-Madison

Event Details
  • Date/Time:
    • Monday February 4, 2013 - Tuesday February 5, 2013
      12:00 pm - 11:59 am
  • Location: Klaus 1116W
  • Phone:
  • URL:
  • Email:
  • Fee(s):
  • Extras:
No contact information submitted.

Summary Sentence: No summary sentence submitted.

Full Summary: No summary paragraph submitted.

Title: Prior Robust Optimization


The 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 prior
distributions and are good candidates for deployment in real systems.

In 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.


Additional Information

In Campus Calendar

College of Computing, School of Computer Science, ARC

Invited Audience
No audiences were selected.
No keywords were submitted.
  • Created By: Elizabeth Ndongi
  • Workflow Status: Published
  • Created On: Jan 30, 2013 - 11:56am
  • Last Updated: Oct 7, 2016 - 10:02pm