[Algoritmi] Algoritmi di approssimazione: quale intervallo?
Sto svolgendo un testo d'esame:
---
Si assuma che il problema di massimizzazione Π sia 3/2-approssimabile. Cosa significa? Data
un’istanza I di Π, in quale intervallo (rispetto alla soluzione ottima m ∗(I )) cade una soluzione approssimata per Π se
soddisfa la proprietà di approssimazione del problema stesso?
---
Per la prima domanda ok, penso di dover mostrare la formula epsilon-approssimante, però quello che non mi è chiaro, è come interagiscono i vari termini della formula, che si lega alla seconda domanda: qual è l'intervallo?
Devo trovare la soluzione ottimale dato epsilon = 3/2?
---
Si assuma che il problema di massimizzazione Π sia 3/2-approssimabile. Cosa significa? Data
un’istanza I di Π, in quale intervallo (rispetto alla soluzione ottima m ∗(I )) cade una soluzione approssimata per Π se
soddisfa la proprietà di approssimazione del problema stesso?
---
Per la prima domanda ok, penso di dover mostrare la formula epsilon-approssimante, però quello che non mi è chiaro, è come interagiscono i vari termini della formula, che si lega alla seconda domanda: qual è l'intervallo?
Devo trovare la soluzione ottimale dato epsilon = 3/2?
Risposte
Vedendo la formula dell'errore relativo, non capisco perché c'è un limite di (1-e) per i problemi di max, e 1/(1-e) per quelli di min
Ciao, vediamo se riesco a darti una mano...
Allora, intanto notiamo dal testo che il problema è 3/2-approssimabile. Perciò siamo nel campo dell'indice di prestazione e non dell'errore relativo, la definizione quindi non è quella dell'epsilon-approssimazione.
Io risolverei il problema così.
Domanda. Si assuma che il problema di massimizzazione \( \Pi \) sia 3/2-approssimabile. Cosa significa ?
Risposta. Se il problema \( \Pi \) è 3/2-approssimabile, allora esiste un algoritmo \( A \) che per ogni input \( x \) determina una soluzione il cui indice di prestazione non è maggiore di 3/2. Cioè: \( R_{\Pi}(x,A(x)) \leq 3/2 \).
Domanda. Data un’istanza \( I \) di \( \Pi \), in quale intervallo (rispetto alla soluzione ottima \( m^∗(I) \)) cade una soluzione approssimata per \( \Pi \), se soddisfa la proprietà di approssimazione del problema stesso?
Risposta. Siccome il problema \( \Pi \) è di massimizzazione la soluzione approssimata, da un algoritmo \( A \) 3/2-approssimante, per una istanza \( I \), cade nell'intervallo \( [\frac {m^*(I)}{3/2}, m^*(I)] \). Cioè: \( \frac {m^*(I)}{3/2} \leq m(I,A(I)) \leq m^*(I) \).
Allora, intanto notiamo dal testo che il problema è 3/2-approssimabile. Perciò siamo nel campo dell'indice di prestazione e non dell'errore relativo, la definizione quindi non è quella dell'epsilon-approssimazione.
Io risolverei il problema così.
Domanda. Si assuma che il problema di massimizzazione \( \Pi \) sia 3/2-approssimabile. Cosa significa ?
Risposta. Se il problema \( \Pi \) è 3/2-approssimabile, allora esiste un algoritmo \( A \) che per ogni input \( x \) determina una soluzione il cui indice di prestazione non è maggiore di 3/2. Cioè: \( R_{\Pi}(x,A(x)) \leq 3/2 \).
Domanda. Data un’istanza \( I \) di \( \Pi \), in quale intervallo (rispetto alla soluzione ottima \( m^∗(I) \)) cade una soluzione approssimata per \( \Pi \), se soddisfa la proprietà di approssimazione del problema stesso?
Risposta. Siccome il problema \( \Pi \) è di massimizzazione la soluzione approssimata, da un algoritmo \( A \) 3/2-approssimante, per una istanza \( I \), cade nell'intervallo \( [\frac {m^*(I)}{3/2}, m^*(I)] \). Cioè: \( \frac {m^*(I)}{3/2} \leq m(I,A(I)) \leq m^*(I) \).
grazie, ora lo leggo cercadno di capire!
edit:
dici basta quello per risolvere? In effetti quadra! grazie, erano giorni che stavo cercando soluzione
edit:
dici basta quello per risolvere? In effetti quadra! grazie, erano giorni che stavo cercando soluzione
tu che corso stai seguendo?
Beh non so se basta, ma io non saprei cosa altro dire 
Io sto ho appena finito di seguire le lezioni del corso di Complessità Computazionale quindi non sono preparatissimo, devo ancora guardarmi bene la teoria.
Io sto ho appena finito di seguire le lezioni del corso di Complessità Computazionale quindi non sono preparatissimo, devo ancora guardarmi bene la teoria.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo