There is a sign-up schedule for this event that can be found at

http://apps.cs.utexas.edu/talkschedules/cgi/list_events.cgi

Type o

f Talk: ACT Seminar

Speaker/Affiliation: Evdokia Nikolova/Texas A&M Un

iversity

Talk Audience: UTCS Faculty, Graduate Students, Undergradua

te Students, and Outside Interested Parties

Date/Time: Friday, April
27, 2012, 11:00 am

Location: ACES 3.408

Host: Vijaya Ramachand

ran

Talk Title: Risk-averse Combinatorial Optimization

Talk Abstr

act:
Optimization has played a key role in making the task of decision ma

king from art to science in the past century. An important challenge that s

till remains is our ability to incorporate the uncertainty in our knowledge
and risk-aversion in our objective. A simple but insightful example of thi

s is encapsulated in the decision question: given a number of route choices

, which shall I choose? Interestingly, this simple question (easily solva

ble in a deterministic setting) becomes highly non-trivial when we incorpor

ate the uncertainty of delays and the individual''s risk-aversion. This pri

marily stems from the combinatorial nature of the problem coupled with the

non-convexity of the objective.

In this talk I explain how to solve th

is reliable route planning problem, and mention how its solution has been

adapted in the MIT CarTel system for routing, which incorporates real traf

fic information (cartel.csail.mit.edu). I then show how the solution extend

s to a general framework of risk-averse combinatorial optimization, for wh

ich I present exact and approximation algorithms. These general-purpose alg

orithms can also cope with combinatorial problems that are NP-hard, whose

deterministic versions we only know how to approximate. At the end, I tou

ch upon how the risk-averse framework provides a foundation for studying eq

uilibria in stochastic network games.

Speaker Bio:
Evdokia Nikolo

va is an Assistant Professor at the Computer Science & Engineering Departme

nt at Texas A&M University. Previously she was a postdoctoral associate in

the Computer Science and Artificial Intelligence Laboratory at MIT. She gra

duated with a BA in Applied Mathematics with Economics from Harvard Univers

ity, MS in Mathematics from Cambridge University, U.K. and Ph.D. in Compu

ter Science from MIT. She is interested in algorithms arising in stochastic
optimization, networks and economics with applications to complex systems

.