Algoritmo di approssimazione: differenze tra le versioni

Versione delle 22:08, 26 dic 2016

Versione delle 17:49, 11 mar 2017

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