Algoritmo di approssimazione: differenze tra le versioni

Versione delle 22:08, 26 dic 2016

Versione attuale delle 16:58, 2 feb 2025

(4 versioni intermedie di 3 utenti non mostrate)

Riga 7:

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.

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

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

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 è mostrato che gli algoritmi di approssimazione elaborati nel 1974 da 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.

==Garanzie di prestazione ==

Riga 56:

Ormai ci sono parecchie tecniche standard che si usano per progettare un algoritmo di approssimazione. Queste comprendono le seguenti.

# [[Algoritmo greedy]]

# [[Ricerca locale (ottimizzazione)|Ricerca locale]]

# Enumerazione e [[programmazione dinamica]]

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

Riga 66:

Nella letteratura, un rapporto di approssimazione per un problema di massimizzazione (minimizzazione) di ''c'' - ϵ (min: ''c'' + ϵ) significa che l'algoritmo ha un rapporto di approssimazione di ''c'' ∓ ϵ per un arbitrario ϵ > 0 ma che il rapporto non si mostra (o non si può mostrare) per ϵ = 0. Un esempio di questo è il rapporto ottimale di inapprossimabilità — inesistenza dell'approssimabilità — di 7 / 8 + ϵ per le istanze soddisfacibili di [[MAX-3SAT]] dovuto a [[Johan Håstad]].<ref name="hastad99someoptimal">{{cita pubblicazione|titolo=Some Optimal Inapproximability Results|rivista=Journal of the ACM|anno=1999|url=http://www.nada.kth.se/~johanh/optimalinap.ps|autore=[[Johan Håstad]]}}</ref> Come menzionato in precedenza, quando ''c'' = 1, si dice che il problema ha uno [[schema di approssimazione in tempo polinomiale]].

Un termine ϵ può apparire quando un algoritmo di approssimazione introduce un errore moltiplicativo e un errore costante mentre l'ottimo minimo delle istanze di dimensione ''n'' va a infinito quando lo fa ''n''. In questo caso, il rapporto di approssimazione è ''c'' ∓ ''k'' / OPT = ''c'' ∓ o(1) per alcune costanti ''c'' e ''k''. Dato un arbitarioarbitrario ϵ > 0, si può scegliere un ''N'' grande abbastanza tale che il termine ''k'' / OPT < ϵ per ogni ''n ≥ N''. Per ogni ϵ fisso, le istanze di dimensione ''n < N'' possono essere risolte mediante la [[Metodo forza bruta|forza bruta]], mostrando in tal modo un rapporto di approssimazione — esistenza di algoritmi di approssimazione con una garanzia — di ''c'' ∓ ϵ per ogni ϵ > 0.

==Note==

Riga 86:

==Collegamenti esterni==

* {{FOLDOC|approximation algorithm|approximation algorithm}}

* Pierluigi Crescenzi, Viggo Kann, Magnús Halldórsson, [[Marek Karpinski]] e Gerhard Woeginger, [http://www.nada.kth.se/~viggo/wwwcompendium/ ''A compendium of NP optimization problems''].

Riga 91 ⟶ 92:

{{Portale|Informatica|Matematica}}

[[Categoria:Algoritmi|Approssimazione]]

[[Categoria:Teoria della complessità computazionale]]