Whereas deterministic optimization problems are formulated with known parameters, in practical applications the exact values of the input data are often not known in advance. Robust optimization is one of the frameworks for modelling optimizations problems that involve uncertainty. One of the criteria of the robust optimization is the min-max regret criterion. Our objective is to briefly present this criterion, summarize some results about its complexity on classical combinatorial problems and, due to the complexity of the resulting problems, summarize some general results about approximation. Finally, we present two new applications:“Minmax regret version of a time-dependent shortest path problem” and “Robust minmax regret discrete optimization problems with investments”.