← Lab · Chapter: Principles of approximation algorithms

Tight instances

Next Fit, extended greedy and LPT on families of instances: the ratio with the optimum approaches the guarantee, which cannot be improved. Choose the algorithm; move \(q\) or press ▶ next to the slider: the parameter grows by one every 0.9 s.