BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Optimization under Uncertainty: Understanding the Correlation Gap 
 - Shipra Agrawal\, Stanford
DTSTART:20110404T090000Z
DTEND:20110404T100000Z
UID:TALK30423@talks.cam.ac.uk
CONTACT:Microsoft Research Cambridge Talks Admins
DESCRIPTION:When faced with the challenge of making decisions in presence 
 of multiple uncertainties\, a common simplifying heuristic is to assume in
 dependence among various sources. Although popular\, the effect of this he
 uristic on the solution quality is little understood. In this talk\, I wil
 l examine the risk associated with ignoring correlations by introducing a 
 new concept of 'Correlation Gap'. Correlation gap captures the price of co
 rrelations in stochastic optimization -- a small correlation gap will impl
 y that the efficient heuristic of assuming independence is actually robust
  against any adversarial correlations\, while a large correlation will sug
 gest that it is important to invest more in data collection and learning c
 orrelations. Additionally\, I will demonstrate that the problem of boundin
 g correlation gap appears as a fundamental question when analyzing the app
 roximation ratios achieved by some randomized algorithmic strategies for d
 eterministic combinatorial optimization problems. I will use function prop
 erties such as monotonicity and submodularity\, and employ techniques of c
 ross-monotonic cost-sharing schemes from game theory in a novel manner to 
 provide a tight characterization of functions with small correlation gap. 
 Results include small constant bounds for cost functions resulting from ma
 ny popular applications such as stochastic facility location\, Steiner tre
 e network design\, minimum spanning tree\, single-source rent-or-buy netwo
 rk design etc.\n\nTowards the end of the talk\, I will briefly discuss my 
 research on some other topics\, including algorithms for online optimizati
 on and techniques for prediction market design.
LOCATION:Large lecture theatre\, Microsoft Research Ltd\, 7 J J Thomson Av
 enue (Off Madingley Road)\, Cambridge
END:VEVENT
END:VCALENDAR