The course will be given by Sandip Banerjee.
It will cover the following topics:
1) Metric Embedding into normed spaces
2) Dimension Reduction
3) Doubling dimension, Epsilon-nets, VC-dimension
4) Nearest neighbor search and its approximation
5) Embedding into trees and Probabilistic embedding
6) Euclidean TSP
7) Approximate Sparsest Cut
Pre-requisite: (i) Algorithm course.(ii) Basic idea of Linear programming and probability
will help but not mandatory.
Literature: A large part of the course will follow the books:
(i) Geometric approximation algorithms (Author- Sariel Har-Peled)
(ii) Algorithmic geometry (Author- J.D. Boissonnat, Mariette Yvinec and
Herve Bronniman)
