Algoritmo di approssimazione: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
Nessun oggetto della modifica |
|||
Riga 28:
:R(x,y) = <math> \max \left ( \frac{OPT}{f(y)}, \frac{f(y)}{OPT} \right ),</math>
dove ''f''(''y'') è il valore/costo della soluzione ''y'' per l'istanza ''x''. Chiaramente, la garanzia di prestazione è maggiore di o uguale a 1 se e solo se ''y'' è una soluzione ottima. Se un algoritmo ''A'' garantisce di restituire soluzioni con una garanzia di prestazione al massimo di ''r''(''n''), allora si dice che ''A'' è un algoritmo di approssimazione ''r''(''n'') e ha un ''rapporto di approssimazione'' di ''r''(''n''). Similmente, un problema con un algoritmo di approssimazione ''r''(''n'') si dice che è ''r''(''n'')
Si può notare che, per i problemi di minimizzazione, le due diverse garanzie forniscono lo stesso risultato e che, per i problemi di massimizzazione, una garanzia di prestazione relativa di ρ è equivalente a una garanzia di prestazione di <math>r = \rho^{-1}</math>. Nella letteratura, entrambe le definizioni sono comuni ma è chiaro qual è la definizione usata da allora, per i problemi di massimizzazione, in quanto ρ ≤ 1 mentre r ≥ 1.
Riga 70:
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/>
| |||