Show simple item record

dc.contributor.authorDemange, Marc
dc.contributor.authorPaschos, Vangelis
dc.date.accessioned2009-12-14T13:24:27Z
dc.date.available2009-12-14T13:24:27Z
dc.date.issued1996
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/2688
dc.descriptionhttp://www.ehess.fr/revue-msh/recherche.php?numero=135en
dc.description.abstractfrA 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.en
dc.language.isoenen
dc.subjectCombinatoireen
dc.subjectAlgorithmes - Algorithmiqueen
dc.subject.ddc511en
dc.titleValeurs extrémales d'un problème d'optimisation combinatoire et approximation polynomialeen
dc.typeArticle accepté pour publication ou publié
dc.contributor.editoruniversityotherUniversité Paris 1, Paris;France
dc.relation.isversionofjnlnameMathématiques, Informatique et Sciences Humaines
dc.relation.isversionofjnlvol135en
dc.relation.isversionofjnldate1996
dc.description.sponsorshipprivateouien
dc.relation.isversionofjnlpublisherEHESSen
dc.subject.ddclabelPrincipes généraux des mathématiquesen


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record