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.
-
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.
-
Tight instances
Next Fit, extended greedy and LPT on families of instances: the ratio with the optimum approaches the guarantee, which cannot be improved.