Algoritmi di approssimazione¶
Parte 5 del corso, volume 5 delle dispense: capitoli 34–40.
Algoritmi di approssimazione: rapporti di prestazione e schemi di approssimazione, con algoritmi e analisi del caso peggiore per lo zaino, il bin packing, il TSP metrico e lo scheduling su macchine parallele, e i limiti dell'approssimazione per la colorazione dei vertici, la clique massima e il TSP generale.
-
34. Principi degli algoritmi di approssimazione
Algoritmi di approssimazione · Schemi di approssimazione
Problemi di zaino¶
-
35. Algoritmi di approssimazione per lo zaino
Notazione · Oggetto critico e capacità residua · L'algoritmo greedy · L'algoritmo Ext-Greedy
Problemi di packing¶
-
36. Algoritmi di approssimazione per il bin packing
Notazione · Next Fit · La classe Any Fit · Proprietà di riempimento a metà
Problemi di colorazione¶
-
37. Colorazione dei vertici: limiti dell'approssimazione
Notazione · Il VCP non è approssimabile · Casi particolari · Esempi
Problemi di clique¶
-
38. Clique massima: limiti dell'approssimazione
Notazione · Il MCP non è approssimabile · Casi particolari · Esempio
Problemi di routing¶
-
39. TSP: il caso generale e il caso metrico
Il TSP generale non è approssimabile · Un caso particolare: il TSP metrico · L'algoritmo del doppio albero e l'algoritmo di Christofides · Proprietà strutturali
Problemi di scheduling¶
-
40. Approssimazione per P||Cmax
Notazione · Gli algoritmi \(LIST\) e \(LPT\) · Una proprietà del list scheduling · Garanzie di prestazione