The main objective of the polynomial approximation is the development of polynomial time algorithms for NP-hard problems, these algorithms guaranteeing feasible solutions lying “as near as possible” to the optimal ones. This work is the fist part of a couple of papers where we introduce the key-concepts of the polynomial approximation and present the main lines of a new formalism. Our purposes are, on the one hand, to present this theory and its objectives and, on the other hand, to discuss the...
Cet article est la suite de l’article «Autour de nouvelles notions pour l’analyse des algorithmes d’approximation : formalisme unifié et classes d’approximation» où nous avons présenté et discuté, dans le cadre d’un nouveau formalisme pour l’approximation polynomiale (algorithmique polynomiale à garanties de performances pour des problèmes NP-difficiles), des outils permettant d’évaluer, dans l’absolu, les proporiétés d’approximation de problèmes difficiles. Afin de répondre pleinement à l’objectif...
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 must be...
Cet article est le premier d'une série de deux articles où
nous présentons les principales caractéristiques d'un nouveau
formalisme pour l'approximation polynomiale (algorithmique
polynomiale à garanties de performances pour les problèmes
-difficiles). Ce travail est l'occasion d'un
regard critique sur ce domaine et de discussions sur la pertinence
des notions usuelles. Il est aussi l'occasion de se familiariser
avec l'approximation polynomiale, de comprendre ses enjeux et
ses méthodes. Ces deux...
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 la connaît et...
We first motivate and define a notion of asymptotic
differential approximation ratio. For this, we introduce a new class of
problems called radial problems including in particular the hereditary
ones. Next, we validate the definition of the asymptotic differential
approximation ratio by proving positive, conditional and negative
approximation results for some combinatorial problems. We first derive a
differential approximation analysis of a classical greedy algorithm for
bin packing, the “first...
Download Results (CSV)