Schema di approssimazione in tempo polinomiale

Da Wikipedia, l'enciclopedia libera.
Vai alla navigazione Vai alla ricerca

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.[1]

È 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.

Varianti[modifica | modifica wikitesto]

Deterministico[modifica | modifica wikitesto]

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(nc) 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.[2] 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.[3]

A meno che P = NP, vale che FPTAS ⊊ PTAS ⊊ APX.[4] 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 per ciascun fisso.

Randomizzato[modifica | modifica wikitesto]

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.[2]

Note[modifica | modifica wikitesto]

  1. ^ Sanjeev Arora, "Polynomial-time Approximation Schemes for Euclidean TSP and other Geometric Problems", Journal of the ACM, 45(5), pp. 753–782, 1998.
  2. ^ a b Vijay V. Vazirani, Approximation Algorithms, Berlino, Springer, 2003, pp. 294–295, ISBN 3-540-65367-8.
  3. ^ H. Kellerer, U. Pferschy e D. Pisinger, Knapsack Problems, Springer, 2004.
  4. ^ Thomas Jansen, Introduction to the Theory of Complexity and Approximation Algorithms, in Ernst W. Mayr, Hans Jürgen Prömel e Angelika Steger (a cura di), Lectures on Proof Verification and Approximation Algorithms, Springer, 1998, 5–28, DOI:10.1007/BFb0053011, ISBN 9783540642015.. Vedi la discuezione che segue la Definizione 1.30 a p. 20.

Collegamenti esterni[modifica | modifica wikitesto]