A Short Survey of Aproximation Algorithms for Combinatorial Optimization under Uncertainty

This paper briefly describes three well-established frameworks for handling uncertainty in optimization problems. Our focus is mainly on combinatorial optimization and on the development of approximation algorithms under the discussed frameworks. In particular, we give a brief overview of Stochastic Programming, Robust Optimization, and Probabilistic Combinatorial Optimization, and list approximation results from the wealth of recent literature on combinatorial problems under these disciplines