giovedì 18 dicembre 2008
Lezione del 18/12/2008
Problemi di ottimizzazione. L'esistenza di un algoritmo polinomiale per un problema di ottimizzazione il cui corrispondente decisionale e' NP-Completo implica P=NP. Algoritmi di approssimazione polinomiale per problemi di ottimizzazione il cui corrispondente decisionale e' NP-Completo. Un algoritmo 2-approssimante per il problema del Min Vertex Cover.
Iscriviti a:
Commenti sul post (Atom)
Nessun commento:
Posta un commento