Vai al contenuto

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.

    Apri l'app →

  • 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.

    Apri l'app →

  • 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.

    Apri l'app →