Some leftovers from ../2004-04-15, particularly showing that SUBSET SUM is NP-hard (see PvsNp).

New stuff is on ApproximationAlgorithms for NP-hard problems, with examples:

- 2-approximation for VERTEX COVER
- 2-approximation for TSP with triangle inequality
- Non-approximability of TSP without triangle inequality
- Fully polynomial-time approximation scheme for SUBSET SUM and KNAPSACK.

We also discussed the perils of implementing algorithms in TECO, a notorious text editor/programming language from 1962.