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(n^1/ε) o anche in O(n^exp(1/ε)) conta come un PTAS.

Varianti

Deterministico

Un problema pratico con gli algoritmi PTAS è che l'esponente del polinomiale potrebbe aumentare drammaticamente quando ε si contrae, ad esempio se il tempo di esecuzione è O(n^(1/ε)!). Un modo di affrontare questo problema è definire lo schema di approssimazione efficiente in tempo polinomiale (in inglese ''efficient polynomial-time approximation scheme o EPTAS), nel quale si richiede che il tempo di esecuzione sia O(n^c) per una c costante indipendente da ε. Questo assicura che un aumento della dimensione del problema abbia lo stesso effetto relativo sul tempo di esecuzione indipendentemente da quale ε venga usato; tuttavia, la costante sotto O-grande può ancora dipendere arbitrariamente da ε. Ancora più restrittivo, e più utile in pratica, è lo schema di approssimazione in tempo pienamente polinomiale (fully polynomial-time approximation scheme o FPTAS), che richiede che l'algoritmo sia polinomiale tanto nella dimensione n del problema quanto in 1/ε. Tutti i problemi in FPTAS sono trattabili a parametri fissi. Un esempio di un problema che ha un FPTAS è il problema dello zaino.

Qualsiasi problema di ottimizzazione fortemente NP-difficile con una funzione obiettivo limitata polinomialmente non può avere un FPTAS a meno che P=NP. Tuttavia, l'inverso viene meno: ad es. se P non è uguale a NP, lo zaino con due limiti non è fortemente NP-difficile, ma non ha un FPTAS anche quando l'obiettivo ottimale è limitato polinomialmente.

A meno che P = NP, vale che FPTAS ⊊ PTAS ⊊ APX. Conseguentemente, in base a questa assunzione, i problemi APX-difficili non hanno PTAS.

Un'altra variante deterministica del PTAS è lo schema di approssimazione in tempo quasi-polinomiale (quasi-polynomial-time approximation scheme o QPTAS). Un QPTAS ha complessità temporale $n^{polylog(n)}$ per ciascun $ϵ>0$ fisso.

Randomizzato

Alcuni problemi che non hanno un PTAS possono ammettere un algoritmo randomizzato con proprietà simili, uno schema di approssimazione randomizzato in tempo polinomiale (polynomial-time randomized approximation scheme o PRAS). Un PRAS è un algoritmo che prende un'istanza di un problema di ottimizzazione o di conteggio e un parametro ε > 0 e, in tempo polinomiale, produce una soluzione che ha un'alta probabilità di essere entro un fattore ε dall'ottimale. Convenzionalmente, "alta probabilità" significa probabilità maggiore di 3/4, benché come con la maggior parte delle classi di complessità probabilistiche la definizione sia robusta rispetto a variazioni di questo valore esatto. Come un PTAS, un PRAS deve avere un tempo di esecuzione polinomiale in n, ma non necessariamente in ε; con ulteriori restrizioni sul tempo di esecuzione in ε, si può definire uno schema di approssimazione randomizzato efficiente in tempo polinomiale (efficient polynomial-time randomized approximation scheme o EPRAS) simile all'EPTAS, e uno schema di approssimazione randomizzato in tempo pienamente polinomiale (fully polynomial-time randomized approximation scheme o FPRAS) simile al FPTAS.

Collegamenti esterni

• Complexity Zoo: PTAS Template:Webarchive, EPTAS Template:Webarchive, FPTAS Template:Webarchive
• Pierluigi Crescenzi, Viggo Kann, Magnús Halldórsson, Marek Karpinski, and Gerhard Woeginger, A compendium of NP optimization problems – elenca i problemi di ottimizzazione NP dotati di PTAS.