Displaying similar documents to “Autour de nouvelles notions pour l'analyse des algorithmes d'approximation : formalisme unifié et classes d'approximation”

Valeurs extrémales d'un problème d'optimisation combinatoire et approximation polynomiale

Marc Demange, Vangelis Th. Paschos (1996)

Mathématiques et Sciences Humaines

Similarity:

A la suite de quelques-uns de nos travaux antérieurs sur la théorie de la complexité et de l'approximation polynomiale, nous présentons quelques nouvelles réflexions et arguments sur les valeurs (et solutions) extrérmales, (optimale et pire), des problèmes d'optirnisation combinatoire. Cette discussion nous conduit à considérer la limite entre constructibilité et non-constructibilité, source constante de contradiction en théorie de la complexité. En effet, cette théorie, telle qu'on...

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...