schema di approssimazione in tempo polinomiale

In informatica, uno schema di approssimazione in tempo polinomiale (in inglese polynomial-time approximation scheme o PTAS) è un tipo di algoritmo di approssimazione per problemi di ottimizzazione (molto spesso, problemi di ottimizzazione NP-difficili). Un PTAS è un algoritmo che prende un'istanza di un problema di ottimizzazione e un parametro ε > 0 e, in tempo polinomiale, produce una soluzione che è ottimale entro un fattore 1 + ε (o 1 - ε per i problemi di massimizzazione). Ad esempio, per il problema euclideo del commesso viaggiatore, un PTAS produrrebbe un giro di lunghezza al massimo (1 + ε)L, con L che è la lunghezza del giro più breve. È richiesto che il tempo di esecuzione di un PTAS sia un tempo polinomiale in n per ogni ε fisso, ma può essere diverso per diversi ε. Così un algoritmo eseguito nel O(n1/ε) o anche in O(nexp(1/ε)) conta come un PTAS.