Schema di approssimazione in tempo polinomiale

Da Wikipedia, l'enciclopedia libera.
(Reindirizzamento da FPTAS)
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]

Estratto da "https://it.wikipedia.org/w/index.php?title=Schema_di_approssimazione_in_tempo_polinomiale&oldid=120737544"