SPEAKER: Katrina Ligett

TIME: Wednesday 12-1pm, December 13, 2006

PLACE: NSH 1507

TITLE: Approximate Online Optimization

ABSTRACT:
Imagine a FedEx driver who must repeatedly choose a route to visit a set
of cities.  Each day, she chooses a tour and then finds out the total time that it
took. The time a street takes may vary unpredictably from day to day due to traffic,
construction, accidents, or any other cause. Her goal is to achieve low average time
over many days.  More generally, in an online sequential linear optimization
problem, a decision-maker selects daily from a known (possibly infinite) set of
decisions, and experiences a cost determined by the next function in an unknown
sequence of cost functions chosen from a known family of linear functions. The
offline version of the FedEx driver''''s problem is simply the Traveling Salesman
Problem, where the edge costs are known in advance.
                                                                    
  
In previous work, Kalai and Vempala (COLT ''''03) showed how to convert any exact
offline algorithm for a linear optimization problem into an algorithm for the online
sequential version of the problem.  They also applied their technique to a special
class of approximation algorithms. Unfortunately, many problems (e.g. the TSP above)
cannot be solved efficiently offline, and many approximation algorithms do not fall
into this special class.
 
 
In this talk, we show how to convert any approximation algorithm for a linear
optimization problem into an algorithm for the online sequential version of the
problem.  Our reduction maintains the asymptotic approximation guarantee of the
original algorithm, relative to the average performance of the best static decision
in hindsight (e.g. best TSP tour).  Our approach is based on a geometric
interpretation of this class of problems.
 
 
Joint work with Sham Kakade and Adam Tauman Kalai.