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...
This survey presents major results and issues related to the study of NPO problems in dynamic environments, that is, in settings where instances are allowed to undergo some modifications over time. In particular, the survey focuses on two complementary frameworks. The first one is the reoptimization framework, where an instance that is already solved undergoes some local perturbation. The goal is then to make use of the information provided by the initial solution to compute a new solution. The...
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...
In on-line computation, the instance of the problem dealt is not
entirely known from the beginning of the solution process, but it
is revealed step-by-step. In this paper we deal with on-line
independent set. On-line models studied until now for this problem
suppose that the input graph is initially empty and revealed
either vertex-by-vertex, or cluster-by-cluster. Here we present a
new on-line model quite different to the ones already studied. It
assumes that a superset of the final graph is initially...
This survey presents major results and issues related to the study of NPO problems in dynamic environments, that is, in settings where instances are allowed to undergo some modifications over time. In particular, the survey focuses on two complementary frameworks. The first one is the reoptimization framework, where an instance that is already solved undergoes some local perturbation. The goal is then to make use of the information provided by the initial solution to compute a new solution. The...
Download Results (CSV)