• 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 - No thumbnail

Thoughts about new notions for the analysis of approximation algorithms

Demange, Marc; Paschos, Vangelis (2002), Thoughts about new notions for the analysis of approximation algorithms. https://basepub.dauphine.fr/handle/123456789/6857

Type
Document de travail / Working paper
External document link
http://hal.archives-ouvertes.fr/hal-00004188/en/
Date
2002
Publisher
Université Paris-Dauphine
Published in
Paris
Pages
62
Metadata
Show full item record
Author(s)
Demange, Marc
Paschos, Vangelis
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. 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.
Subjects / Keywords
NP; NP-complete; complexity; polynomial approximation

Related items

Showing items related by title and author.

  • Thumbnail
    Autour de nouvelles notions pour l'analyse des algorithmes d'approximation : formalisme unifié et classes d'approximation 
    Demange, Marc; Paschos, Vangelis (2002) Article accepté pour publication ou publié
  • Thumbnail
    Approximation algorithms for minimum set covering problem: a survey 
    Paschos, Vangelis; Demange, Marc (1994) Article accepté pour publication ou publié
  • Thumbnail
    Differential approximation algorithms for some combinatorial optimization problems 
    Demange, Marc; Grisoni, Pascal; Paschos, Vangelis (1998) 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
    Complexity and approximation results for the min weighted node coloring problem 
    Escoffier, Bruno; Demange, Marc; Paschos, Vangelis; de Werra, Dominique; Monnot, Jérôme (2008) Chapitre d'ouvrage
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