Algoritmo di approssimazione: differenze tra le versioni

Versione delle 22:23, 22 mar 2014

Versione delle 22:46, 22 mar 2014

Riga 10:

Non tutti gli algoritmi di approssimazione sono adatti per tutte le applicazioni pratiche. Spesso usano risolutori IP/LP/[[Programmazione semidefinita|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(''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 [[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 appicazioni 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.

<!--

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

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

Inapproximability has been a fruitful area of research in computational complexity theory since the 1990 result of Feige, Goldwasser, Lovasz, Safra and Szegedy on the inapproximability of [[Independent set (graph theory)|Independent Set]]. After Arora et al. proved the [[PCP theorem]] a year later, it has now been shown that Johnson's 1974 approximation algorithms for Max SAT, Set Cover, Independent Set and Coloring all achieve the optimal approximation ratio, assuming P != NP.

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 (teoria dei grafi)|insieme indipendente]]. Dopo che Arora et al. dimostrarono il [[teorema PCP]] un anno dopo, si è ormai mostrato che gli algoritmi di approssimazione del 1974 di 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.

<!--

== Performance guarantees ==

For some approximation algorithms it is possible to prove certain properties about the approximation of the optimum result. For example, a '''''ρ''-approximation algorithm''' ''A'' is defined to be an algorithm for which it been proven that the value/cost, ''f''(''x''), of the approximate solution ''A''(''x'') to an instance ''x'' will not be more (or less, depending on the situation) than a factor ''ρ'' times the value, OPT, of an optimum solution.