Geometric Approximation Algorithms (Spring 25)

Lectures

1. 1/22/25. L1: k-center clustering
   General introduction, k-center clustering, greedy clustering algorithm, greedy permutation, proof that the greedy $k$-center clustering algorithm is a $2$-approximation.
   Clustering (5.1, 5.2).
2. 1/27/25. L2: Coresets for clustering: notes.
3. 1/29/25. L3: Grids, closest pair: Notes.
4. 2/3/25. L4: Introduction to Geometric Sampling.
   Approximation: Notations and stuff.
   nets, samples, and relative approximations.
   I got a bit carried away in the lecture. The final part is from Section 6 of this paper.
   Anyway, we covered $k$-center $2$-approximation clustering algorithm that runs in linear time.
5. 2/5/25. L5: Pack & prune: Notes.
6. 2/10/25. L5: Pack & prune II
7. 2/12/25. L6: Quadtree: notes.
8. 2/17/25 and 2/19/25. L7/8: WSPD: notes.
9. 2/24/25. L9: VC dimension: VC dimension.
10. 3/3/25. L10: Reweighting: Spanning tree with low crossing number11.
11. 3/10/25. L12: Approximate depth: notes.
12. 3/12/25. L13: Approximate depth continued.
13. 3/24/25. L14: LSH: Locality sensitive hashing.
14. 3/26/25. L15: JL Lemma: Johnson-Lindenstruass lemma.
15. 4/2/25. L16: JL continued.
16. 4/4/25. L17: Partitions.
17. 4/9/25. L18: Partitions continued
18. 4/14/25. L19: large margin classifier
19. 4/16/25. L20: No dimensional geometric algorithms
20. 4/23/25. L21: The Frechet distance
21. 4/23/25. L22
22. 4/30/25 (Wed. L23: Shifting Independent set of unit disks, shifting technique.
23. 5/5/25 L26: Convexity and weak ε-nets.