Two ways to escape an intractable problem: give up on determinism, or give up on optimality.
Randomization
- Randomized Algorithms — the framework
- Las Vegas vs Monte Carlo
- Random Shuffling and Anti-Hash Defence
- Birthday Paradox and Collision Bounds
- Reservoir Sampling
- Randomized Heuristics — hill climbing, restarts
- Simulated Annealing
- Karger · Karger-Stein
- Pollard’s Rho · Miller-Rabin
- Treap and other randomized structures — see Treap
Approximation
- Approximation Algorithms — ratios, PTAS, FPTAS
- Greedy Approximations — set cover, vertex cover
- Christofides (metric TSP, 3/2)
- Goemans-Williamson (MAX-CUT, 0.878)
- Randomized Rounding
- Karmarkar-Karp (number partitioning)
See also: Complexity Theory · Exact / NP-Hard