Algoritmi Approssimazione - Massimizzazione & Minimizzaz

[markzzz]

Ciao a tutti!!! Cercherò di essere il più breve possibile.

Se ho un algoritmo di approssimazione e stò minimizzando, avrò la seguente :

$0
Con Vertex Cover avrò $C<=2C*$ ,ergo ottengo :

$0
Quindi la soluzione che troverò sarà compresa tra C* e (massimo) 2C* (anche se non riesco a vedere uno scenario in cui trovo dei vertici che siano tra C* e 2C*, mi vien da pensare che l'algoritmo mi trovi sempre il valore di 2C*).

Ora però, per un algoritmo di approssimazione dove massimizzo, avrò la seguente :

$0
Ma quindi con MAX-3-CNF ottengo $C>=8/7C*$ ? Non credo altrimenti la formula sarebbe

$0<8/7C*<=C<=C*$

E non può essere $C*>=8/7C*$

Le mie domande quindi sono le seguenti :

1 - C come lo definisco per un problema di massimizzazione (per esempio, appunto, in MAX-3-CNF)?
2 - Ma se C può spaziare (nell'esempio di minimizzazione di vertex cover) tra C* e 2C* questo significa che volendo potrei anche trovare la soluzione ottima? E allora perchè è di approssimazione?

Spero si possa far luce su questo enigma!

Saluti

[hamming_burst]

Sicuro di aver capito per cosa stanno C e C* ?

C = soluzione algoritmo approssimato
C* = soluzione ottima

Mi sa che hai un po' di confusione. La soluzione ottima non si sa dov'è. Se sei su una linea retta e rappresenti lo spazio di ricerca per la soluzione ottima e la soluziona k-approssimata:


<_____C________C*(ma può essere ovunque)_______________________2C____________2C*_________>

La soluzione approssimata spazia, sì tra C* e 2C*, ma per arrivare a 2C utilizzi un algoritmo polinomiale, che verifica casi finiti e locali. C* può essere ovunque tra C e 2C ma sei sicuro che è in questo spazio, facendo osì crei dei limiti sullo spazio di ricerca dell'ottimo (che non si può trovare, o se hai un culo grandissimo forse si).

C lo si definisce caso per caso, tipo nel taglio massimo è collegato al numero egli archi. Non ricordo bene il caso SAT mi sembra che è collegato alla sommatoria della probabilità uniforme dei letterarli, essendo che la scelta è random, si cerca di approssimare alla massima soddisfacibilità della formula.

Dimenticavo una cosa, l'appossimazione di C vale sia con i problemi di minimimo che con quelli di massimo, c'è una relazione del genere $max(C/(C*), (C*)/C)$.

[markzzz]

Clear;)