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