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

⏮◀◀▶▶STEP0.25x1xZOOM

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.

← lagrange-multipliers greedy-algorithms →