Laboratorio interattivo¶
Qui le garanzie di approssimazione si toccano con mano: ogni app esegue un algoritmo passo per passo sulle istanze di riferimento del corso, che si possono anche cambiare. Scegli un'app: si apre a tutta pagina. Tutto gira nel browser; i numeri sono calcolati dall'algoritmo, non scritti a mano.
Algoritmi di approssimazione¶
-
Zaino 0/1: greedy, Ext-Greedy, H² e FPTAS
Gli algoritmi di approssimazione del capitolo passo per passo, con il rapporto z(I)/A(I); nell'FPTAS i profitti scalati e la PD sui profitti.
-
TSP metrico: double tree e Christofides
Albero ricoprente minimo, accoppiamento dei vertici dispari, circuito euleriano e scorciatoie, sull'istanza di riferimento, sugli esercizi e sulle famiglie tight.
-
Istanze tight
Next Fit, greedy esteso e LPT su famiglie di istanze: il rapporto con l'ottimo si avvicina alla garanzia, che non si può migliorare.