Skip to content

Interactive lab

Here you can get your hands on approximation guarantees: each app runs an algorithm step by step on the reference instances of the course, which you can also change. Pick an app: it opens full page. Everything runs in the browser; the numbers are computed by the algorithm, not typed by hand.

Approximation algorithms

  • 0/1 KP: greedy, Ext-Greedy, H² and FPTAS


    The approximation algorithms of the chapter step by step, with the ratio z(I)/A(I); in the FPTAS the scaled profits and the DP by profits.

    Open the app →

  • Metric TSP: double tree and Christofides


    Minimum spanning tree, matching of the odd vertices, Eulerian circuit and shortcutting, on the reference instance, on the exercises and on the tight families.

    Open the app →

  • Tight instances


    Next Fit, extended greedy and LPT on families of instances: the ratio with the optimum approaches the guarantee, which cannot be improved.

    Open the app →