BSc seminar in the course "Approximation Algorithms (252-4910-00L)" at ETH Zurich.
Presentation of Lagrangian Relaxation and the k-Median Problem based on chapter 7.7 of the textbook "The design of approximation algorithms" (Williamson & Shmoys, 2011) and the excellent Microsoft Research talk by Sara Ahmadian: https://www.microsoft.com/en-us/research/video/clustering-and-facility-location-problems/.