Approximation Algorithm for Metric k-Center using Parametric Pruning

I present a 2-approximation algorithm for the metric k-center problem. This algorithm is based on parametric pruning (and is not the greedy algorithm you might know). This is then extended to a 3-approximation for the metric weighted-center problem
00:00 Metric k-Center
03:41 Parametric Pruning
07:44 G_j
10:41 Dominating Set
12:17 Square of a graph
18:02 Independent Set
19:44 Lemma for lower bound
23:30 Algorithm
24:19 Analysis
27:14 Tightness
28:28 Approximation lower bound
33:41 Metric-Weighted-Center
35:29 Algorithm
40:15 Tightness