dc.contributor.author Demange, Marc dc.contributor.author Paschos, Vangelis dc.date.accessioned 2011-07-29T14:35:30Z dc.date.available 2011-07-29T14:35:30Z dc.date.issued 2002 dc.identifier.uri https://basepub.dauphine.fr/handle/123456789/6857 dc.language.iso en en dc.subject NP en dc.subject NP-complete en dc.subject complexity en dc.subject polynomial approximation en dc.subject.ddc 003 en dc.title Thoughts about new notions for the analysis of approximation algorithms en dc.title.alternative Réflexion autour de nouvelles notions pour l’analyse des algorithmes d’approximation en dc.type Document de travail / Working paper dc.description.abstracten 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. We first introduce the key-concepts of the polynomial approximation and then we 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 appropriateness and the pertinence of its constitutive elements, as people knew them until now, and to propose their enrichment. The different stages of this work are accompanied by several illustrative examples. So, this paper is addressed to both domain researchers and non-specialist readers. We particularly quote the great interest, both theoretical and operational, to construct an internal structure for the class NPO (of the optimization problems in NP). For this reason we devise the notions presented in two categories. The tools of the former allow the individual evaluation of the approximability properties of any NP-hard problem. We present and discuss notions as algorithmic chain, approximation level, or even notions of limits (with respect to algorithmic chains, or to problems instances). The tools of the second category allow the comparison between different problems regarding their respective approximability properties. We find here the central complexity object, the reduction (adapted, of course, in the framework of the polynomial approximation). We propose a new definition unifying the several approximation preserving reductions known in the literature and also extending their scope. We try to justify the interest of this new definition by several speaking examples. The last part of the paper applies the different concepts discussed formerly in the study of the hardness (approximation intractability) of an instance and in the apprehension of the structure of the set of hard instances of a problem. Then, many distinct situations appear, under our point of view, as complementary ones. This part of the paper allows us to also draw directions for further research. en dc.publisher.name Université Paris-Dauphine en dc.publisher.city Paris en dc.identifier.citationpages 62 en dc.identifier.urlsite http://hal.archives-ouvertes.fr/hal-00004188/en/ en dc.description.sponsorshipprivate oui en dc.subject.ddclabel Recherche opérationnelle en
﻿

Files in this item

FilesSizeFormatView

There are no files associated with this item.