Indice completo¶ Tutte le pagine del sito, nell'ordine del menu: i capitoli con le loro sezioni e le altre pagine. Capitoli¶ 1. Principi degli algoritmi di approssimazione · Esercizi 1.1 Algoritmi di approssimazione 1.2 Schemi di approssimazione 1.3 Errori tipici 1.4 In sintesi Problemi di zaino¶ 2. Algoritmi di approssimazione per lo zaino · Esercizi 2.1 Notazione 2.2 Oggetto critico e capacità residua 2.3 L'algoritmo greedy 2.4 L'algoritmo Ext-Greedy 2.5 L'algoritmo \(H^2\) 2.6 L'algoritmo \(H^{\ell}\) 2.7 L'algoritmo Basic-FPTAS 2.8 Garanzie di prestazione 2.9 Garanzia di prestazione assoluta 2.10 Errori tipici 2.11 In sintesi Problemi di packing¶ 3. Algoritmi di approssimazione per il bin packing · Esercizi 3.1 Notazione 3.2 Next Fit 3.3 La classe Any Fit 3.4 Proprietà di riempimento a metà 3.5 Garanzie di prestazione 3.6 Errori tipici 3.7 In sintesi Problemi di colorazione¶ 4. Colorazione dei vertici: limiti dell'approssimazione · Esercizi 4.1 Notazione 4.2 Il VCP non è approssimabile 4.3 Casi particolari 4.4 Esempi 4.5 Fonti 4.6 Errori tipici 4.7 In sintesi Problemi di clique¶ 5. Clique massima: limiti dell'approssimazione · Esercizi 5.1 Notazione 5.2 Il MCP non è approssimabile 5.3 Casi particolari 5.4 Esempio 5.5 Fonti 5.6 Errori tipici 5.7 In sintesi Problemi di routing¶ 6. TSP: il caso generale e il caso metrico · Esercizi 6.1 Il TSP generale non è approssimabile 6.2 Un caso particolare: il TSP metrico 6.3 L'algoritmo del doppio albero e l'algoritmo di Christofides 6.4 Proprietà strutturali 6.5 Garanzie di prestazione 6.6 Fonti 6.7 Errori tipici 6.8 In sintesi Problemi di scheduling¶ 7. Approssimazione per P||Cmax · Esercizi 7.1 Notazione 7.2 Gli algoritmi \(LIST\) e \(LPT\) 7.3 Una proprietà del list scheduling 7.4 Garanzie di prestazione 7.5 Fonti 7.6 Errori tipici 7.7 In sintesi Altre pagine¶ Esercizi Laboratorio Materiale Notebook Colab Autovalutazione