Algorithms in metric spaces 1000-2M25APM
1. Approximation algorithms in planar graphs.
2. Linear programming. The Facility Location problem.
3. Metric embeddings. FRT algorithm for tree embeddings.
4. Clustering. The k-means++ algorithm
5. Euclidean metrics. A coreset for the k-means problem.
6. Dimension reduction. Johnson-Lindenstrauss Lemma.
7. Arora’s algorithm for the Traveling Salesperson Problem in euclidean metrics
8. Algorithms for metrics of bounded doubling dimension
9. Embeddings of graphs into the L1 metric. The Sparsest Cut problem.
Type of course
Requirements
Prerequisites
Course coordinators
Assessment criteria
There will be 3 sets of homework problems, resulting in a modifier to the exam grade from the interval [-1, +1.5]. The course concludes with an oral exam.
Bibliography
1. The Design of Approximation Algorithms, D. P. Williamson, D. B. Shmoys, Cambridge University Press 2012
2. Foundations of Data Science, A. Blum, J. Hopcroft, R. Kannan, Cambridge University Press 2020
Additional information
Information on level of this course, year of study and semester when the course unit is delivered, types and amount of class hours - can be found in course structure diagrams of apropriate study programmes. This course is related to the following study programmes:
- Bachelor's degree, first cycle programme, Computer Science
- Master's degree, second cycle programme, Computer Science
Additional information (registration calendar, class conductors, localization and schedules of classes), might be available in the USOSweb system: