Thumbnail

Optima locaux garantis pour l'approximation différentielle

Monnot, Jérôme; Paschos, Vangelis; Toulouse, Sophie (2003), Optima locaux garantis pour l'approximation différentielle, TSI : Technique et Science Informatiques, 22, 3, p. 257-288. http://dx.doi.org/10.3166/tsi.22.257-288

View/Open
Type
Article accepté pour publication ou publié
Date
2003
Journal name
TSI : Technique et Science Informatiques
Volume
22
Number
3
Publisher
Hermès
Pages
257-288
Publication identifier
Metadata
Show full item record
Author(s)
Monnot, Jérôme cc
Paschos, Vangelis
Toulouse, Sophie cc
Abstract (EN)
We first introduce the class GLO[ ]; it includes optimization problems that guarantee the quality of their local optima, with respect to the differential approximation ratio. Next, we show that a certain number of well-known combinatorial problems belong to this class, while other ones do not. Finally, based upon the results obtained, we place GLO[ ] in the scene of the approximability classes.
Subjects / Keywords
Local search; Local optimization; Complexity; Polynomial approximation; recherche locale; optimisation locale; complexité; approximation polynomiale