Combinatorial Optimization 1
Metric $k$-center
General $k$-center problem statement: Let \((X, d)\) be a metric space where \(X\) is a set and \(d\) is a metric. A set \(V \subseteq X\) is provided together with a parameter \(k\). The goal is to find a subset \(C \subseteq V\) with \(|C| = k\) such that the maximum distance of a point in \(V\) to the closest point in \(C\) is minimized. The problem can be formally defined as follows: Input: a set $V \subseteq X$, and a parameter $k$. Output: a set $C \subseteq V$ of $k$ points. Goal: Minimize the cost $r^C(V) = \max_{v \in V} d(v, C)$ The k-Center Clustering problem can also be defined on a complete undirected graph $G = (V, E)$ as follows: