Approximation and resolution of min-max and min-max regret versions of combinatorial optimization problems

摘要

This is a summary of the most important results presented in the author's PhD thesis. This thesis, written in French, was defended on November 2005 and supervised by Cristina Bazgan and Daniel Vanderpooten. A copy is available from the author upon request. This thesis deals with the complexity, approximation and resolution of the min-max and min-max versions of classical combinatorial optimization problems. In addition to these theoretical aspects, a practical application of robustness approaches to the problem of data association is considered.