• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
Thumbnail

Autour de nouvelles notions pour l'analyse des algorithmes d'approximation : formalisme unifié et classes d'approximation

Demange, Marc; Paschos, Vangelis (2002), Autour de nouvelles notions pour l'analyse des algorithmes d'approximation : formalisme unifié et classes d'approximation, RAIRO, 36, 3, p. 237-277. http://dx.doi.org/10.1051/ro:2003005

View/Open
publi145.pdf (847.8Kb)
Type
Article accepté pour publication ou publié
Date
2002
Journal name
RAIRO
Volume
36
Number
3
Publisher
EDP Sciences
Pages
237-277
Publication identifier
http://dx.doi.org/10.1051/ro:2003005
Metadata
Show full item record
Author(s)
Demange, Marc
Paschos, Vangelis
Abstract (FR)
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 NP-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 articles s'adressent donc autant aux spécialistes qu'aux non spécialistes de ce domaine. Nous insistons tout particulièrement sur l'intérêt, tant théorique qu'opérationnel, de mettre en évidence une structure au sein de la classe NPO des problèmes d'optimisation de NP. Dans ce premier article, nous nous intéressons aux outils qui permettent d'évaluer, dans l'absolu, les propriétés d'approximation de problèmes difficiles. Nous discutons notamment les notions de chaînes d'approximation, de niveau d'approximation, d'ordre de difficulté ainsi que deux notions de limites (par rapport à une suite d'algorithmes et par rapport aux instances). Chaque notion est largement discutée et illustrée par de nombreux exemples choisis essentiellement pour leur valeur pédagogique.
Abstract (EN)
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 appropriateness and the pertinence of its constitutive elements, as people knew them until now, and to propose their enrichment. Henceforth, these papers are addressed to both domain researchers and non-specialist readers. We particularly quote the great theoretical and operational interest in constructing an internal structure for the class NPO (of the optimization problems in NP). In this fist part, we focus on some basic tools allowing the individual evaluation of the approximability properties of any NP-hard problem. We present and discuss notions as algorithmic chain, approximation level, hardness threshold and two notions of limits (with respect to algorithmic chains and with respect to problems instances). The notions dealt in the paper are presented together with several illustrative examples.
Subjects / Keywords
algorithmes d'approximation; analyse des algorithmes et des problèmes; difficulté intrinsèque; complexité

Related items

Showing items related by title and author.

  • Thumbnail
    Quelques étapes vers la conciliation de la théorie d'approximation et celle d'optimisation : une nouvelle théorie d'approximation polynomiale et résultats préliminaires 
    Demange, Marc; Paschos, Vangelis (1993) Article accepté pour publication ou publié
  • Thumbnail
    Approximation polynomiale : notions de difficulté et leur impact pour étudier la structure de NP 
    Demange, Marc; Paschos, Vangelis (2000) Document de travail / Working paper
  • Thumbnail
    Completeness in differential approximation classes 
    Ausiello, Giorgio; Bazgan, Cristina; Demange, Marc; Paschos, Vangelis (2005) Article accepté pour publication ou publié
  • Thumbnail
    Completeness in differential approximation classes 
    Ausiello, Giorgio; Bazgan, Cristina; Demange, Marc; Paschos, Vangelis (2003) Communication / Conférence
  • Thumbnail
    Quelques résultats dans le cadre d'une nouvelle théorie de l'approximation polynomiale 
    Demange, Marc; Grisoni, Pascal; Paschos, Vangelis (1994) Article accepté pour publication ou publié
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo