En informatique, un schéma d'approximation en temps polynomial (en anglais polynomial-time approximation scheme, abrégé en PTAS) est une famille d'algorithmes d'approximation pour des problèmes d'optimisation combinatoire. On dit aussi plus simplement schéma d'approximation polynomial. Le plus souvent, les problèmes d'optimisation combinatoire considérés sont NP-difficiles. Plusieurs variantes des PTAS existent : des définitions plus restrictives comme les EPTAS et FPTAS, ou d'autres qui reposent sur les algorithmes probabilistes comme les PRAS et FPRAS. Un PTAS est un algorithme qui prend en arguments une instance d'un problème d'optimisation et un paramètre et qui produit, en temps polynomial, une solution qui est optimale à un facteur près (ou pour un problème de maximisation). Par exemple, pour le problème du voyageur de commerce euclidien, un PTAS prend en entrée la donnée de n coordonnées dans le plan (ou dans un espace euclidien de dimension d) dans un espace euclidien, ainsi que le paramètre . Le PTAS produit alors un tour dont la longueur est au plus , où est la longueur du tour le plus court. On demande de plus que le temps d'exécution d'un PTAS soit polynomial en la taille de l'instance pour chaque fixé, mais il peut être différent pour des valeurs différentes de . Ainsi, un algorithme en temps ou même en est considéré comme un PTAS. Un problème qui se pose dans la pratique avec les algorithmes PTAS est que l'exposant du polynôme peut croître très rapidement quand diminue, par exemple quand le temps est en Une façon d'y répondre est de définir des schémas d'approximation temps polynomial dits efficaces (en anglais EPTAS pour efficient polynomial-time approximation scheme), pour lesquels on demande un temps d'exécution en pour une constante indépendante de . On est ainsi assuré que l'accroissement la taille du problème a le même effet relatif sur l'accroissement du temps de calcul, indépendamment du choisi ; la constante cachée dans le peut par contre dépendre arbitrairement de .

À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.
Cours associés (10)
MATH-250: Advanced numerical analysis I
Construction and analysis of numerical methods for the solution of problems from linear algebra, integration, approximation, and differentiation.
MGT-418: Convex optimization
This course introduces the theory and application of modern convex optimization from an engineering perspective.
MATH-261: Discrete optimization
This course is an introduction to linear and discrete optimization. Warning: This is a mathematics course! While much of the course will be algorithmic in nature, you will still need to be able to p
Afficher plus
Concepts associés (9)
Ensemble dominant
En théorie des graphes, un ensemble dominant (ou dominating set en anglais) d'un graphe G = ( S, A ) est un sous-ensemble D de l'ensemble S des sommets tel que tout sommet qui n'appartient pas à D possède au moins une arête d'extrémité un sommet de D. Le problème de l'ensemble dominant est de déterminer, étant donné G et un entier naturel k, si G possède un ensemble dominant d'au plus k sommets. Ce problème est NP-complet.
Algorithme d'approximation
En informatique théorique, un algorithme d'approximation est une méthode permettant de calculer une solution approchée à un problème algorithmique d'optimisation. Plus précisément, c'est une heuristique garantissant à la qualité de la solution qui fournit un rapport inférieur (si l'on minimise) à une constante, par rapport à la qualité optimale d'une solution, pour toutes les instances possibles du problème.
Complexité paramétrée
En algorithmique, la complexité paramétrée (ou complexité paramétrique) est une branche de la théorie de la complexité qui classifie les problèmes algorithmiques selon leur difficulté intrinsèque en fonction de plusieurs paramètres sur les données en entrée ou sur la sortie. Ce domaine est étudié depuis les années 90 comme approche pour la résolution exacte de problèmes NP-complets. Cette approche est utilisée en optimisation combinatoire, notamment en algorithmique des graphes, en intelligence artificielle, en théorie des bases de données et en bio-informatique.
Afficher plus

Graph Chatbot

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.