Approximation Algorithms for Offline Risk-averse Combinatorial Optimization

Thursday, March 27, 2014
ENS 637

We consider generic optimization problems that can be formulated as minimizing the cost of a feasible solution w.x over a combinatorial feasible set F ⊂ {0, 1}^n. For these problems we describe a framework of risk-averse stochastic problems where the cost vector W has independent random components, unknown at the time of solution. A natural and important objective that incorporates risk in this stochastic setting is to look for a feasible solution whose stochastic cost has a small tail or a small convex combination of mean and standard deviation. Our models can be equivalently reformulated as nonconvex programs for which no efficient algorithms are known.

We provide efficient general-purpose approximation algorithms. They use as a black-box (exact or approximate) the solution to the underlying deterministic problem and thus immediately apply to arbitrary combinatorial problems. For example, from an available approximation algorithm to the deterministic problem, we construct an approximation algorithm with almost the same approximation factor for the stochastic problem. The algorithms are based on a geometric analysis of the nonlinear level sets of the objective functions.


Assistant Professor

Evdokia Nikolova is an Assistant Professor in the Department of Electrical and Computer Engineering at The University of Texas at Austin. Previously she was an an Assistant Professor at the Computer Science & Engineering Department at Texas A&M University and a postdoctoral associate in the Computer Science and Artificial Intelligence Laboratory at MIT.

She graduated with a B.A. in Applied Mathematics with Economics from Harvard University, M.S. in Mathematics from Cambridge University (U.K.) and Ph.D. in Computer Science from MIT. She is interested in risk analysis from an algorithmic perspective arising in stochastic optimization, networks, economics, and complex systems. She has worked on applications to transportation and is also interested in energy and other domains where her work may apply.