Uncertainty in optimization is not a new ingredient. Diverse modelsconsidering uncertainty have been developed over the last 40 years.In our paper we essentially discuss a particular uncertainty modelassociated with combinatorial optimization problems, developed inthe 90's and broadly studied in the past years. This approach namedminmax regret (in particular our emphasis is on the robustdeviation criteria) is different from the classical approach for handlinguncertainty, stochastic approach, where uncertainty is modeledby assumed probability distributions over the space of all possiblescenarios and the objective is to find a solution with good probabilisticperformance. In the minmax regret (MMR) approach, the set of all possible scenariosis described deterministically, and the search is for a solution thatperforms reasonably well for all scenarios, i.e., that has the bestworst-case performance. In this paper we discuss the computational complexity of some classiccombinatorial optimization problems using MMR approach, analyze thedesign of several algorithms for these problems, suggest the studyof some specific research problems in this attractive area, and alsodiscuss some applications using this model.