Schéma d'approximation en temps polynomial
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 .