Algoritmo di approssimazione: differenze tra le versioni

Versione delle 19:55, 22 mar 2014

Versione delle 21:50, 22 mar 2014

Riga 1:

{{T|inglese|informatica|marzo 2014}}

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.

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

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

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.

<!--

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''²⁰⁰⁰). 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.

Riga 69:

An ϵ-term may appear when an approximation algorithm introduces a multiplicative error and a constant error while the minimum optimum of instances of size ''n'' goes to infinity as ''n'' does. In this case, the approximation ratio is ''c'' ∓ ''k'' / OPT = ''c'' ∓ o(1) for some constants ''c'' and ''k''. Given arbitrary ϵ > 0, one can choose a large enough ''N'' such that the term ''k'' / OPT < ϵ for every ''n ≥ N''. For every fixed ϵ, instances of size ''n < N'' can be solved by brute force , thereby showing an approximation ratio — existence of approximation algorithms with a guarantee — of ''c'' ∓ ϵ for every ϵ > 0.

-->

==Note==

<references/>

== See also Bibliografia==

* {{citecita libro book

* [[Domination analysis]] considers guarantees in terms of the rank of the computed solution.

| lastcognome = Vazirani

| firstnome = Vijay V.

==Citations==

| authorlinklinkautore = Vijay Vazirani

{{More footnotes|date=April 2009}}

| titletitolo = Approximation Algorithms

{{reflist}}

| publishereditore = Springer

| yearanno = 2003

==References==

| ___locationcittà = Berlin

* {{cite book

| last = Vazirani

| first = Vijay V.

| authorlink = Vijay Vazirani

| 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.&nbsp;1022&ndash;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-0521195270}}

==ExternalCollegamenti linksesterni==

* 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==

<references/>

{{Portali|Matematica|Informatica}}

[[Categoria:Algoritmi]]

[[Categoria:Complessità computazionale]]

[[Categoria:Matematica per l'informatica]]