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 pù 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 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 difficili problemi di implememtazione. Inoltre, alcuni algoritmi di approssimazione hanno tempi di esecuzione poco pratici anche se sono in tempo polinomiale, ad esempio O(n2000). 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 appicazioni 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.
Note
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-0521195270.
Collegamenti esterni
- Pierluigi Crescenzi, Viggo Kann, Magnús Halldórsson, Marek Karpinski e Gerhard Woeginger, A compendium of NP optimization problems.
