Nell'[[informatica]] e nella [[ricerca operativa]], un '''algoritmo di approssimazione''' è un [[algoritmo]] usato per trovare soluzioni approssimate a [[Problema di ottimizzazione|problemi di ottimizzazione]]. Gli algoritmi di approssimazione sono spesso associati a problemi [[NP-difficile|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ùpiù per problemi dove gli algoritmi esatti in tempo polinomiale sono noti ma risultano troppo costosi a causa della dimensione dell'input. ▼{{T|inglese|informatica|marzo 2014}}
Un esempio tipico di un algoritmo di approssimazione è quello per la [[Problema della copertura dei vertici|copertura dei vertici]] nei [[Grafo|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.
▲Nell'[[informatica]] e nella [[ricerca operativa]], un '''algoritmo di approssimazione''' è un [[algoritmo]] usato per trovare soluzioni approssimate a [[Problema di ottimizzazione|problemi di ottimizzazione]].Gli algoritmi di approssimazione sono spesso associati a problemi [[NP-difficile|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.
<!--
A typical example for an approximation algorithm is the one for [[Vertex cover problem|vertex cover]] in [[Graph (mathematics)|graph]]s: find an uncovered edge and add ''both'' endpoints to the vertex cover, until none remain. It is clear that the resulting cover is at most twice as large as the optimal one. This is a [[constant factor approximation algorithm]] with a factor of 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 [[Classi di complessità P e NP|P = NP]], come il [[problema della massima cricca]].
NP-hard problems vary greatly in their approximability; some, such as the [[bin packing problem]], can be approximated within any factor greater than 1 (such a family of approximation algorithms is often called a [[polynomial time approximation scheme]] or ''PTAS''). Others are impossible to approximate within any constant, or even polynomial factor unless [[P = NP]], such as the [[maximum clique problem]].
I problemi NP-difficili spesso possono essere espressi come [[Programmazione lineare|programmi interi]] (''integer programs'', IP) e risolti esattamente in [[tempo esponenziale]]. Molti algoritmi di approssimazione emergono dal [[rilassamento della programmazione lineare]] del programma intero.
NP-hard problems can often be expressed as [[integer programs]] (IP) and solved exactly in [[exponential time]]. Many approximation algorithms emerge from the [[linear programming relaxation]] of the integer program.
Non tutti gli algoritmi di approssimazione sono adatti per tutte le applicazioni pratiche. Spesso usano risolutori IP/LP/[[Programmazione semidefinita|semidefiniti]], [[Struttura dati|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''<sup>2000</sup>). 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 [[Problema del commesso viaggiatore#TSP euclideo|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]], [[Trasporto|pianificazione dei trasporti]] e [[Inventario|gestione degli inventari]]. In tali scenari, essi devono competere con le corrispondenti formulazioni IP dirette.
Not all approximation algorithms are suitable for all practical applications. They often use IP/LP/[[semidefinite programming|Semidefinite]] solvers, complex data structures or sophisticated algorithmic techniques which lead to difficult implementation problems. Also, some approximation algorithms have impractical running times even though they are polynomial time, for example O(''n''<sup>2000</sup>). Yet the study of even very expensive algorithms is not a completely theoretical pursuit as they can yield valuable insights. A classic example is the initial PTAS for [[Euclidean traveling salesman problem|Euclidean TSP]] due to [[Sanjeev Arora]] which had prohibitive running time, yet within a year, Arora refined the ideas into a linear time algorithm. Such algorithms are also worthwhile in some applications where the running times and cost can be justified e.g. [[computational biology]], [[financial engineering]], [[transportation planning]], and [[inventory management]]. In such scenarios, they must compete with the corresponding direct IP formulations.
Un'altra limitazione dell'approccio è che esso si applica soltanto ai problemi di ottimizzazione e non ai [[Problema decisionale|problemi di decisione]] "puri" come la [[Soddisfacibilità booleana|soddisfacibilità]], sebbene sia spesso possibile concepire versionsi di ottimizzazione di tali problemi, come il [[problema della massima soddisfacibilità]] (Max SAT).
Another limitation of the approach is that it applies only to optimization problems and not to "pure" [[decision problem]]s like [[boolean satisfiability problem|satisfiability]], although it is often possible to conceive optimization versions of such problems, such as the [[maximum satisfiability problem]] (Max SAT).
InapproximabilityL'inapprossimabilità hasè beenstata aun'area fruitfuldi arearicerca offruttuosa researchnel incampo computationaldella complexity[[teoria theorydella sincecomplessità thecomputazionale]] 1990fin resultdal risultato del 1990 ofdi Feige, Goldwasser, Lovasz, Safra ande Szegedy on the inapproximability ofsull'inapprossimabilità dell'[[IndependentInsieme setindipendente (graphteoria dei theorygrafi)|Independentinsieme Setindipendente]]. Dopo Afterche Arora et al. proveddimostrarono theil [[PCPteorema theoremPCP]] aun yearanno laterdopo, itsi hasè nowmostrato beenche showngli thatalgoritmi Johnson'sdi approssimazione elaborati nel 1974 approximationda algorithmsJohnson forper il Max SAT, Setla Covercopertura degli insiemi, Independentl'insieme indipendente e Setla andcolorazione Coloringraggiungono alltutti achieveil therapporto optimalottimale approximationdi ratioapprossimazione, assumingassumendo P != NP.
==Garanzie di prestazione ==
== Performance guarantees ==
ForPer somealcuni approximationalgoritmi algorithmsdi itapprossimazione isè possiblepossibile toprovare provecerte certainproprietà propertiessull'approssimazione aboutdel therisultato approximation of the optimum resultottimale. ForPer exampleesempio, aun '''algoritmo di approssimazione ''ρ''-approximation algorithm''' ''A'' issi defineddefinisce tocome beun analgoritmo algorithmper foril whichquale itsi beenè provenprovato thatche theil valuevalore/costcosto, ''f''(''x''), ofdella thesoluzione approximate solutionapprossimata ''A''(''x'') toper an instanceun'istanza ''x'' willnon notsarà be morepiù (oro lessmeno, dependingsecondo onla the situationsituazione) thangrande adi factorun fattore ''ρ'' timesvolte rispetto theal valuevalore, OPT, ofdi anuna optimumsoluzione solutionottima.
:<math>\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}</math>
TheIl factorfattore ''ρ'' isè called thechiamato ''relativegaranzia performancedi guaranteeprestazione relativa''. AnUn approximationalgoritmo algorithmdi hasapprossimazione anha una ''absolutegaranzia performancedi guaranteeprestazione assoluta'' oro ''boundederrore errorlimitato'' ''c'', if itse hasè beenstato provenprovato forper everyogni instanceistanza ''x'' thatche
:<math> (\mathrm{OPT} - c) \leq f(x) \leq (\mathrm{OPT} + c).</math>
SimilarlySimilmente, thela ''performancegaranzia guaranteedi prestazione'', ''R''(''x,y''), ofdi auna solutionsoluzione ''y'' toper an instanceun'istanza ''x'' isè defineddefinita ascome
:R(x,y) = <math> \max \left ( \frac{OPT}{f(y)}, \frac{f(y)}{OPT} \right ),</math>
wheredove ''f''(''y'') isè theil valuevalore/costcosto ofdella the solutionsoluzione ''y'' forper the instancel'istanza ''x''. ClearlyChiaramente, thela performancegaranzia guaranteedi isprestazione greaterè thanmaggiore ordi equalo touguale 1 and equal toa 1 ifse ande onlysolo ifse ''y'' isè anuna optimalsoluzione solutionottima. IfSe anun algorithmalgoritmo ''A'' guaranteesgarantisce todi returnrestituire solutionssoluzioni withcon auna performancegaranzia guaranteedi ofprestazione atal mostmassimo di ''r''(''n''), thenallora si dice che ''A'' isè saidun toalgoritmo bedi anapprossimazione ''r''(''n'')-approximation algorithme andha has anun ''approximationrapporto ratiodi approssimazione'' ofdi ''r''(''n''). LikewiseSimilmente, aun problemproblema withcon anun algoritmo di approssimazione ''r''(''n'')-approximation algorithmsi isdice saidche to beè ''r''(''n'')''-''approximableapprossimabile'' oro haveche anha approximationun ratiorapporto ofdi approssimazione di ''r''(''n'').<ref name=ausiello99complexity>{{citecita booklibro|titletitolo=Complexity and Approximation: Combinatorial Optimization Problems and their Approximability Properties|yearanno=1999|authorautore=G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela, ande M. Protasi}}</ref><ref name="kann92onthe">{{citecita booklibro|titletitolo=On the Approximability of NP-complete Optimization Problems|authorautore=Viggo Kann|yearanno=1992|url=http://www.csc.kth.se/~viggo/papers/phdthesis.pdf}}</ref>
OneSi maypuò notenotare thatche, per i forproblemi minimizationdi problemsminimizzazione, thele twodue differentdiverse guaranteesgaranzie provideforniscono thelo samestesso resultrisultato ande thatche, per i forproblemi maximizationdi problemsmassimizzazione, auna garanzia relativedi performanceprestazione guaranteerelativa ofdi ρ isè equivalent toequivalente a performanceuna garanzia di guaranteeprestazione ofdi <math>r = \rho^{-1}</math>. InNella the literatureletteratura, bothentrambe definitionsle aredefinizioni commonsono butcomuni itma isè clearchiaro whichqual definitionè isla useddefinizione since,usata forda maximizationallora problemsper i problemi di massimizzazione, asin quanto ρ ≤ 1 whilementre r ≥ 1.
TheLa ''absolutegaranzia performancedi guaranteeprestazione assoluta'' <math>\Rho_A</math> ofdi someun approximationqualche algorithmalgoritmo di approssimazione ''A'', wheredove ''x'' referssi toriferisce an instanceall'istanza ofdi aun problemproblema, ande wheredove <math>R_A(x)</math> isè thela performancegaranzia guaranteedi ofprestazione di ''A'' onsu ''x'' (i.e.cioè ρ forper l'istanza problemdel instanceproblema ''x'') isè:
:<math> \Rho_A = \inf \{ r \geq 1 \mid R_A(x) \leq r, \forall x \}.</math>
ThatQuesto isvuol todire say thatche <math>\Rho_A</math> isè theil largestlimite boundpiù ongrande thesul approximationrapporto ratiodi approssimazione, ''r'', thatche onesi seesvede oversu alltutte possiblele instancespossibili ofistanze thedel problemproblema. LikewiseSimilmente, theil ''asymptoticrapporto di performanceprestazione ratioasintotica'' <math>R_A^\infty</math> isè:
:<math> R_A^\infty = \inf \{ r \geq 1 \mid \exists n \in \mathbb{Z}^+, R_A(x) \leq r, \forall x, |x| \geq n\}. </math>
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.
That is to say that it is the same as the ''absolute performance ratio'', with a lower bound ''n'' on the size of problem instances. These two types of ratios are used because there exist algorithms where the difference between these two is significant.
{| class="wikitable"
|+Garanzie di prestazione
|+Performance guarantees
|-
! !! ''r''-approxappross.<ref name="ausiello99complexity"/><ref name="kann92onthe"/> !! ''ρ''-approxappross. !! errore rel. error<ref name="kann92onthe"/> !! errore rel. error<ref name="ausiello99complexity"/> !! norm.errore rel. errornorm.<ref name="ausiello99complexity"/><ref name="kann92onthe"/> !! abs.errore errorass.<ref name="ausiello99complexity"/><ref name="kann92onthe"/>
|-
! max: <math>f(x) \geq</math>
|}
==Tecniche di progettazione degli algoritmi==
==Algorithm design techniques==
Ormai ci sono parecchie tecniche standard che si usano per progettare un algoritmo di approssimazione. Queste comprendono le seguenti.
By now there are several standard techniques that one tries to design an approximation algorithm. These include the following ones.
# [[GreedyAlgoritmo algorithmgreedy]]
# [[Ricerca locale]]
# [[Local search (optimization)|Local search]]
# Enumerazione e [[programmazione dinamica]]
# Enumeration and [[dynamic programming]]
# 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.
# Solving a [[convex programming]] relaxation to get a fractional solution. Then converting this fractional solution into a feasible solution by some appropriate rounding. The popular relaxations include the following.
## Rilassamento della [[programmazione lineare]]
## [[Linear programming]] relaxation
## Rilassamento della [[programmazione semidefinita]]
## [[Semidefinite programming]] relaxation
# Incorporare il problema in qualche metrica semplice e poi risolverlo sulla metrica. Questa è conosciuta anche come incoporazione metrica.
# Embedding the problem in some simple metric and then solving the problem on the metric. This is also known as metric embedding.
== EpsilonTermini termsepsilon ==
InNella the literatureletteratura, anun approximationrapporto ratiodi forapprossimazione aper maximizationun problema di massimizzazione (minimizationminimizzazione) problem ofdi ''c'' - ϵ (min: ''c'' + ϵ) meanssignifica thatche thel'algoritmo algorithmha hasun anrapporto approximationdi ratioapprossimazione ofdi ''c'' ∓ ϵ forper arbitraryun arbitrario ϵ > 0 butma thatche theil ratiorapporto hasnon notsi mostra (oro cannot)non besi shownpuò mostrare) forper ϵ = 0. AnUn exampleesempio ofdi thisquesto isè theil optimalrapporto inapproximabilityottimale di inapprossimabilità — inexistenceinesistenza of approximationdell'approssimabilità — ratio ofdi 7 / 8 + ϵ forper satisfiablele istanze soddisfacibili di [[MAX-3SAT]] instancesdovuto due toa [[Johan Håstad]].<ref name="hastad99someoptimal">{{citecita journalpubblicazione|titletitolo=Some Optimal Inapproximability Results|journalrivista=Journal of the ACM|yearanno=1999|url=http://www.nada.kth.se/~johanh/optimalinap.ps|authorautore=[[Johan Håstad]]}}</ref> AsCome mentionedmenzionato previouslyin precedenza, whenquando ''c'' = 1, thesi problemdice ische saidil toproblema haveha auno [[polynomial-timeschema di approssimazione in approximationtempo schemepolinomiale]].
AnUn termine ϵ-term maypuò appearapparire whenquando anun approximationalgoritmo algorithmdi introducesapprossimazione aintroduce multiplicativeun errorerrore andmoltiplicativo ae constantun errorerrore whilecostante thementre minimuml'ottimo optimumminimo ofdelle instancesistanze ofdi sizedimensione ''n'' goesva toa infinityinfinito asquando lo fa ''n'' does. In thisquesto casecaso, theil approximationrapporto ratiodi isapprossimazione è ''c'' ∓ ''k'' / OPT = ''c'' ∓ o(1) forper somealcune constantscostanti ''c'' ande ''k''. GivenDato arbitraryun arbitrario ϵ > 0, onesi can choose apuò largescegliere enoughun ''N'' suchgrande thatabbastanza thetale termche il termine ''k'' / OPT < ϵ forper everyogni ''n ≥ N''. ForPer every fixedogni ϵ fisso, instancesle istanze ofdi sizedimensione ''n < N'' canpossono beessere solvedrisolte bymediante brutela force[[Metodo forza bruta|forza bruta]], therebymostrando showingin antal approximationmodo ratioun rapporto di approssimazione — existenceesistenza ofdi approximationalgoritmi algorithmsdi withapprossimazione acon una guaranteegaranzia — ofdi ''c'' ∓ ϵ forper everyogni ϵ > 0.
== See also Note==
* [[Domination analysis]] considers guarantees in terms of the rank of the computed solution.
==CitationsBibliografia==
* {{cita libro
{{More footnotes|date=April 2009}}
| cognome = Vazirani
{{reflist}}
| nome = Vijay V.
| linkautore = Vijay Vazirani
==References==
| titletitolo = Approximation Algorithms ▼* {{cite book
| lasteditore = VaziraniSpringer
| firstanno = Vijay V.2003
| authorlinkcittà = Vijay VaziraniBerlin
▲ | title = Approximation Algorithms
| publisher = Springer
| year = 2003
| ___location = Berlin
| isbn = 3-540-65367-8 }}
* [[Thomas H. Cormen]], [[Charles E. Leiserson]], [[Ronald L. Rivest]], ande [[Clifford Stein]]. ''[[Introduction to Algorithms]]'', Second2ª Editionedizione. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. ChapterCapitolo 35: "Approximation AlgorithmsAlgorithm"s, pp. 1022–10561022–1056.
* [[Dorit H. Hochbaum]], ed(cur.), ''[[Approximation Algorithms for NP-Hard problems]]'', PWS Publishing Company, 1997. ISBN 0-534-94968-1. ChapterCapitolo 9: "Various Notions of Approximations: Good, Better, Best, and More".
* {{Citationcita testo|last1cognome1=Williamson|first1nome1=David P.|last2cognome2=Shmoys|first2nome2=David B.|authorlink2wkautore2=David Shmoys|datedata=April 26, aprile 2011|titletitolo=The Design of Approximation Algorithms|___locationcittà=|publishereditore=[[Cambridge University Press]]|isbn=978-05211952700-521-19527-0}}
==ExternalCollegamenti linksesterni==
* {{FOLDOC|approximation algorithm|approximation algorithm}}
* Pierluigi Crescenzi, Viggo Kann, Magnús Halldórsson, [[Marek Karpinski]] ande Gerhard Woeginger, [http://www.nada.kth.se/~viggo/wwwcompendium/ ''A compendium of NP optimization problems''].
-->
==Note==
{{Controllo di autorità}}
{{Portali|Matematica|Informatica}}
{{Portale|Informatica|Matematica}}
[[Categoria:Complessità computazionaleAlgoritmi|Approssimazione]]
[[Categoria:MatematicaTeoria perdella l'informaticacomplessità computazionale]]
| 