← ~/visualizations

approximation-algorithms

Visualizes the formal performance guarantee of a ρ-approximation: a polynomial-time algorithm produces a feasible solution ALG whose cost (or value) is within a multiplicative factor ρ of the optimal OPT. Animated bars show OPT, the algorithm’s output, and the bound ρ·OPT while the inequality ALG/OPT ≤ ρ is highlighted.

canvasclick to interact
t=0s

practical uses

  • 01.Designing fast near-optimal solutions for NP-hard problems (e.g., set cover, vertex cover, TSP variants)
  • 02.Reasoning about worst-case solution quality guarantees in production heuristics
  • 03.Comparing algorithms by provable bounds when exact optimization is infeasible

technical notes

Time-based 4s animation cycle: OPT and ALG bars animate in, then the bound line ρ·OPT appears and the inequality tokens are highlighted in sequence. Values are generated to always satisfy ALG/OPT ≤ ρ. Uses grid-snapped coordinates for a blocky aesthetic, green-on-black palette, and responsive scaling via scale = min(w,h)/240.