BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//talks.cam.ac.uk//v3//EN
BEGIN:VTIMEZONE
TZID:Europe/London
BEGIN:DAYLIGHT
TZOFFSETFROM:+0000
TZOFFSETTO:+0100
TZNAME:BST
DTSTART:19700329T010000
RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=-1SU
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0100
TZOFFSETTO:+0000
TZNAME:GMT
DTSTART:19701025T020000
RRULE:FREQ=YEARLY;BYMONTH=10;BYDAY=-1SU
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
CATEGORIES:Microsoft Research Cambridge\, public talks
SUMMARY:Optimization under Uncertainty: Understanding the
Correlation Gap - Shipra Agrawal\, Stanford
DTSTART;TZID=Europe/London:20110404T100000
DTEND;TZID=Europe/London:20110404T110000
UID:TALK30423AThttp://talks.cam.ac.uk
URL:http://talks.cam.ac.uk/talk/index/30423
DESCRIPTION:When faced with the challenge of making decisions
in presence of multiple uncertainties\, a common s
implifying heuristic is to assume independence amo
ng various sources. Although popular\, the effect
of this heuristic on the solution quality is littl
e understood. In this talk\, I will examine the ri
sk associated with ignoring correlations by introd
ucing a new concept of 'Correlation Gap'. Correlat
ion gap captures the price of correlations in stoc
hastic optimization -- a small correlation gap wil
l imply that the efficient heuristic of assuming i
ndependence is actually robust against any adversa
rial correlations\, while a large correlation will
suggest that it is important to invest more in da
ta collection and learning correlations. Additiona
lly\, I will demonstrate that the problem of bound
ing correlation gap appears as a fundamental quest
ion when analyzing the approximation ratios achiev
ed by some randomized algorithmic strategies for d
eterministic combinatorial optimization problems.
I will use function properties such as monotonicit
y and submodularity\, and employ techniques of cro
ss-monotonic cost-sharing schemes from game theory
in a novel manner to provide a tight characteriza
tion of functions with small correlation gap. Resu
lts include small constant bounds for cost functio
ns resulting from many popular applications such a
s stochastic facility location\, Steiner tree netw
ork design\, minimum spanning tree\, single-source
rent-or-buy network design etc.\n\nTowards the en
d of the talk\, I will briefly discuss my research
on some other topics\, including algorithms for o
nline optimization and techniques for prediction m
arket design.
LOCATION:Large lecture theatre\, Microsoft Research Ltd\, 7
J J Thomson Avenue (Off Madingley Road)\, Cambrid
ge
CONTACT:Microsoft Research Cambridge Talks Admins
END:VEVENT
END:VCALENDAR