Autour de nouvelles notions pour l'analyse des algorithmes d'approximation : de la structure de NPO à la structure des instances
Marc Demange, Vangelis Paschos (2010)
RAIRO - Operations Research
Similarity:
This paper is the continuation of the paper “” where a new formalism for polynomial approximation and its basic tools allowing an “absolute” (individual) evaluation the approximability properties of -hard problems have been presented and discussed. In order to be used for exhibiting a structure for the class (the optimization problems of ), these tools must be enriched with an “instrument” allowing comparisons between approximability properties of different problems (these comparisons...