• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Aide
  • Connexion
  • Langue 
    • Français
    • English
Consulter le document 
  •   Accueil
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • Consulter le document
  •   Accueil
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • Consulter le document
JavaScript is disabled for your browser. Some features of this site may not work without it.

Afficher

Toute la baseCentres de recherche & CollectionsAnnée de publicationAuteurTitreTypeCette collectionAnnée de publicationAuteurTitreType

Mon compte

Connexion

Enregistrement

Statistiques

Documents les plus consultésStatistiques par paysAuteurs les plus consultés
Thumbnail - Request a copy

Valeurs extrémales d'un problème d'optimisation combinatoire et approximation polynomiale

Demange, Marc; Paschos, Vangelis (1996), Valeurs extrémales d'un problème d'optimisation combinatoire et approximation polynomiale, Mathématiques, Informatique et Sciences Humaines, 135

Type
Article accepté pour publication ou publié
Date
1996
Nom de la revue
Mathématiques, Informatique et Sciences Humaines
Volume
135
Éditeur
EHESS
Métadonnées
Afficher la notice complète
Auteur(s)
Demange, Marc
Paschos, Vangelis
Résumé (FR)
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émales, (optimale et pire), des problèmes d'optimisation 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 manie aujourd'hui, est fondée sur la non-constructibilité tandis que deux de ses domaines principaux, l'optimisation combinatoire et la théorie de l'approximation polynomiale, nécessitent un cadre conceptuel fondé sur la constructibilité. L'approximation polynomiale dépasse aujourd'hui sa conception originelle (en tant qu'ensemble d'outils pour la résolution rapide des problèmes NP-complets), intervient très fortement dans la définition de nouvelles notions et objets mathématiques et fait ainsi partie à part entière de "l'arsenal" de la complexité. Elle est un outil théorique majeur pour l'appréhension, l'approfondissement et l'enrichissement de la théorie de la complexité et notamment de la connaissance de la classe NP. Ces développements récents de l'approximation polynomiale dévoilent des problèmes particulièrement intéressants, notamment d'un point de vue épistémologique.
Mots-clés
Combinatoire; Algorithmes - Algorithmique

Publications associées

Affichage des éléments liés par titre et auteur.

  • Vignette de prévisualisation
    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é
  • Vignette de prévisualisation
    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é
  • Vignette de prévisualisation
    On an approximation measure founded on the links between optimization and polynomial approximation theory 
    Demange, Marc; Paschos, Vangelis (1996) Article accepté pour publication ou publié
  • Vignette de prévisualisation
    Approximation polynomiale : notions de difficulté et leur impact pour étudier la structure de NP 
    Demange, Marc; Paschos, Vangelis (2000) Document de travail / Working paper
  • Vignette de prévisualisation
    Polynomial approximation algorithms with performance guarantees: an introduction-by-example 
    Demange, Marc; Paschos, Vangelis (2005) Article accepté pour publication ou publié
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Tél. : 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo