Algoritmo di approssimazione

Nell'informatica e nella ricerca operativa, un algoritmo di approssimazione è un algoritmo usato per trovare soluzioni approssimate a problemi di ottimizzazione. Gli algoritmi di approssimazione sono spesso associati a problemi NP-difficili; poiché è improbabile che ci possano essere algoritmi esatti efficienti in tempo polinomiale che risolvono problemi NP-difficili, ci si accontenta di soluzioni subottimali in tempo polinomiale. Diversamente dall'euristica, che di solito trova soluzioni ragionevolmente buone in tempi ragionevolmente veloci, in questo caso si vogliono soluzioni di qualità dimostrabile e tempi di esecuzione con limiti dimostrabili. Idealmente, l'approssimazione è ottimale fino a un piccolo fattore costante (ad esempio entro il 5% della soluzione ottimale). Gli algoritmi di approssimazione sono usati sempre di più per problemi dove gli algoritmi esatti in tempo polinomiale sono noti ma risultano troppo costosi a causa della dimensione dell'input.

Un esempio tipico di un algoritmo di approssimazione è quello per la copertura dei vertici nei grafi: trovare uno spigolo scoperto e aggiungere "entrambi" gli estremi alla copertura dei vertici, finché non ne rimane nessuno. È chiaro che la copertura risultante è al massimo due volte più grande di quella ottimale. Questo è un algoritmo di approssimazione a fattore costante con un fattore di 2.

I problemi NP-difficili variano grandemente nella loro approssimabilità; alcuni, come il problema dell'impacchettamento, può essere approssimato entro un qualsiasi fattore maggiore di 1 (tale famiglia di algoritmi di approssimazione è chiamata spesso schema di approssimazione in tempo polinomiale o PTAS). Altri sono impossibili da approssimare entro qualsiasi costante, o perfino fattore polinomiale, a meno che P = NP, come il problema della massima cricca.

I problemi NP-difficili spesso possono essere espressi come programmi interi (integer programs, IP) e risolti esattamente in tempo esponenziale. Molti algoritmi di approssimazione emergono dal rilassamento della programmazione lineare del programma intero.

Non tutti gli algoritmi di approssimazione sono adatti per tutte le applicazioni pratiche. Spesso usano risolutori IP/LP/semidefiniti, strutture dati complesse o tecniche algoritmiche sofisticate che conducono a problemi di difficile implementazione. Inoltre, alcuni algoritmi di approssimazione hanno tempi di esecuzione poco pratici anche se sono in tempo polinomiale, ad esempio O(n²⁰⁰⁰). Tuttavia lo studio di algoritmi anche molto costosi non è una ricerca completamente teorica, in quanto possono fornire preziose intuizioni. Un esempio classico è il PTAS iniziale per il TSP euclideo dovuto a Sanjeev Arora che aveva un tempo di esecuzione proibitivo; tuttavia entro un anno, Arora perfezionò le idee in un algoritmo in tempo lineare. Tali algoritmi sono validi anche in alcune applicazioni dove i tempi e il costo di esecuzione possono essere giustificati, ad es. biologia computazionale, ingegneria finanziaria, pianificazione dei trasporti e gestione degli inventari. In tali scenari, essi devono competere con le corrispondenti formulazioni IP dirette.

Un'altra limitazione dell'approccio è che esso si applica soltanto ai problemi di ottimizzazione e non ai problemi di decisione "puri" come la soddisfacibilità, sebbene sia spesso possibile concepire versionsi di ottimizzazione di tali problemi, come il problema della massima soddisfacibilità (Max SAT).

L'inapprossimabilità è stata un'area di ricerca fruttuosa nel campo della teoria della complessità computazionale fin dal risultato del 1990 di Feige, Goldwasser, Lovasz, Safra e Szegedy sull'inapprossimabilità dell'insieme indipendente. Dopo che Arora et al. dimostrarono il teorema PCP un anno dopo, si è mostrato che gli algoritmi di approssimazione elaborati nel 1974 da Johnson per il Max SAT, la copertura degli insiemi, l'insieme indipendente e la colorazione raggiungono tutti il rapporto ottimale di approssimazione, assumendo P != NP.

Garanzie di prestazione

Per alcuni algoritmi di approssimazione è possibile provare certe proprietà sull'approssimazione del risultato ottimale. Per esempio, un algoritmo di approssimazione ρ A si definisce come un algoritmo per il quale si è provato che il valore/costo, f(x), della soluzione approssimata A(x) per un'istanza x non sarà più (o meno, secondo la situazione) grande di un fattore ρ volte rispetto al valore, OPT, di una soluzione ottima.

${\begin{cases}\mathrm {OPT} \leq f(x)\leq \rho \mathrm {OPT} ,\qquad {\mbox{if }}\rho >1;\\\rho \mathrm {OPT} \leq f(x)\leq \mathrm {OPT} ,\qquad {\mbox{if }}\rho <1.\end{cases}}$

Il fattore ρ è chiamato garanzia di prestazione relativa. Un algoritmo di approssimazione ha una garanzia di prestazione assoluta o errore limitato c, se è stato provato per ogni istanza x che

$(\mathrm {OPT} -c)\leq f(x)\leq (\mathrm {OPT} +c).$

Similmente, la garanzia di prestazione, R(x,y), di una soluzione y per un'istanza x è definita come

R(x,y) = $\max \left({\frac {OPT}{f(y)}},{\frac {f(y)}{OPT}}\right),$

dove f(y) è il valore/costo della soluzione y per l'istanza x. Chiaramente, la garanzia di prestazione è maggiore di o uguale a 1 se e solo se y è una soluzione ottima. Se un algoritmo A garantisce di restituire soluzioni con una garanzia di prestazione al massimo di r(n), allora si dice che A è un algoritmo di approssimazione r(n) e ha un rapporto di approssimazione di r(n). Similmente, un problema con un algoritmo di approssimazione r(n) si dice che è r(n)-approssimabile o che ha un rapporto di approssimazione di r(n).

Si può notare che, per i problemi di minimizzazione, le due diverse garanzie forniscono lo stesso risultato e che, per i problemi di massimizzazione, una garanzia di prestazione relativa di ρ è equivalente a una garanzia di prestazione di $r=\rho ^{-1}$. Nella letteratura, entrambe le definizioni sono comuni ma è chiaro qual è la definizione usata da allora per i problemi di massimizzazione, in quanto ρ ≤ 1 mentre r ≥ 1.

La garanzia di prestazione assoluta $\mathrm {P} _{A}$ di un qualche algoritmo di approssimazione A, dove x si riferisce all'istanza di un problema, e dove $R_{A}(x)$ è la garanzia di prestazione di A su x (cioè ρ per l'istanza del problema x) è:

$\mathrm {P} _{A}=\inf\{r\geq 1\mid R_{A}(x)\leq r,\forall x\}.$

Questo vuol dire che $\mathrm {P} _{A}$ è il limite più grande sul rapporto di approssimazione, r, che si vede su tutte le possibili istanze del problema. Similmente, il rapporto di prestazione asintotica $R_{A}^{\infty }$ è:

$R_{A}^{\infty }=\inf\{r\geq 1\mid \exists n\in \mathbb {Z} ^{+},R_{A}(x)\leq r,\forall x,|x|\geq n\}.$

Questo vuol dire che è lo stesso del rapporto di prestazione assoluta, con un limite inferiore n sulla dimensione delle istanze del problema. Questi due tipi di rapporti si usano perché esistono algoritmi dove la differenza tra i due è significativa.

Garanzie di prestazione

	r-appross.	ρ-appross.	errore rel.	errore rel.	errore rel. norm.	errore ass.
max: $f(x)\geq$	$r^{-1}\mathrm {OPT}$	$\rho \mathrm {OPT}$	$(1-c)\mathrm {OPT}$	$(1-c)\mathrm {OPT}$	$(1-c)\mathrm {OPT} +c\mathrm {WORST}$	$\mathrm {OPT} -c$
min: $f(x)\leq$	$r\mathrm {OPT}$	$\rho \mathrm {OPT}$	$(1+c)\mathrm {OPT}$	$(1-c)^{-1}\mathrm {OPT}$	$(1-c)^{-1}\mathrm {OPT} +c\mathrm {WORST}$	$\mathrm {OPT} +c$

Tecniche di progettazione degli algoritmi

Ormai ci sono parecchie tecniche standard che si usano per progettare un algoritmo di approssimazione. Queste comprendono le seguenti.

1. Algoritmo greedy
2. Ricerca locale
3. Enumerazione e programmazione dinamica
4. Risolvere un rilassamento della programmazione convessa per ottenere una soluzione frazionaria. Poi convertire questa soluzione frazionaria in una soluzione fattibile mediante qualche arrotondamento appropriato. I rilassamenti più conosciuti includono i seguenti.
   1. Rilassamento della programmazione lineare
   2. Rilassamento della programmazione semidefinita
5. Incorporare il problema in qualche metrica semplice e poi risolverlo sulla metrica. Questa è conosciuta anche come incoporazione metrica.

Termini epsilon

Nella letteratura, un rapporto di approssimazione per un problema di massimizzazione (minimizzazione) di c - ϵ (min: c + ϵ) significa che l'algoritmo ha un rapporto di approssimazione di c ∓ ϵ per un arbitrario ϵ > 0 ma che il rapporto non si mostra (o non si può mostrare) per ϵ = 0. Un esempio di questo è il rapporto ottimale di inapprossimabilità — inesistenza dell'approssimabilità — di 7 / 8 + ϵ per le istanze soddisfacibili di MAX-3SAT dovuto a Johan Håstad. Come menzionato in precedenza, quando c = 1, si dice che il problema ha uno schema di approssimazione in tempo polinomiale.

Un termine ϵ può apparire quando un algoritmo di approssimazione introduce un errore moltiplicativo e un errore costante mentre l'ottimo minimo delle istanze di dimensione n va a infinito quando lo fa n. In questo caso, il rapporto di approssimazione è c ∓ k / OPT = c ∓ o(1) per alcune costanti c e k. Dato un arbitrario ϵ > 0, si può scegliere un N grande abbastanza tale che il termine k / OPT < ϵ per ogni n ≥ N. Per ogni ϵ fisso, le istanze di dimensione n < N possono essere risolte mediante la forza bruta, mostrando in tal modo un rapporto di approssimazione — esistenza di algoritmi di approssimazione con una garanzia — di c ∓ ϵ per ogni ϵ > 0.

Bibliografia

• Vijay V. Vazirani, Approximation Algorithms, Berlin, Springer, 2003, ISBN 3-540-65367-8.
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, e Clifford Stein. Introduction to Algorithms, 2ª edizione. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Capitolo 35: "Approximation Algorithm"s, pp. 1022–1056.
• Dorit H. Hochbaum (cur.), Approximation Algorithms for NP-Hard problems, PWS Publishing Company, 1997. ISBN 0-534-94968-1. Capitolo 9: "Various Notions of Approximations: Good, Better, Best, and More".
• David P. Williamson e David B. Shmoys, The Design of Approximation Algorithms, Cambridge University Press, 26 aprile 2011, ISBN 978-0-521-19527-0.

Collegamenti esterni

• Pierluigi Crescenzi, Viggo Kann, Magnús Halldórsson, Marek Karpinski e Gerhard Woeginger, A compendium of NP optimization problems.