"Algorithms for Risk-averse Combinatorial Optimization"
Event details
| Date | 17.03.2011 |
| Hour | 16:15 |
| Speaker | Dr. Evdokia Nikolova, MIT, IC Faculty Candidate |
| Location |
INM10
|
| Category | Conferences - Seminars |
Abstract:
Optimization has played a key role in making the task of decision
making from art to science in the past century. An important challenge
that still remains is our ability to incorporate the uncertainty in
our knowledge and risk-aversion in our objective. A simple but
insightful example of this is encapsulated in the decision question:
given a number of route choices, which shall I choose? Interestingly,
this simple question (easily solvable in a deterministic setting)
becomes highly non-trivial when we incorporate the uncertainty of
delays and the individual’s risk-aversion. This primarily stems from
the combinatorial nature of the problem coupled with the non-convexity
of the objective.
In this talk I explain how to solve this reliable route planning
problem, and mention how its solution has been adapted in the MIT
CarTel system for routing, which incorporates real traffic information
(cartel.csail.mit.edu). I then show how the solution extends to a
general framework of risk-averse combinatorial optimization, for which
I present exact and approximation algorithms. These general-purpose
algorithms can also cope with combinatorial problems that are NP-hard,
whose deterministic versions we only know how to approximate. At the
end, I touch upon how the risk-averse framework provides a foundation
for studying equilibria in stochastic network games.
Bio: Evdokia Nikolova is a postdoctoral associate in the Computer Science
and Artificial Intelligence Laboratory at MIT. She graduated with a
BA in Applied Mathematics with Economics from Harvard University, MS
in Mathematics from the Statistical Laboratory at Cambridge
University, U.K. and Ph.D. in Computer Science from MIT.
She is interested in algorithms arising in stochastic optimization,
networks and economics.
Links
Practical information
- General public
- Free
Contact
- Christine Moscioni