Centre Selection Problem

computation algorithms optimisation

Definition

Center Selection Problem

Given a set of $n$ sites $S=\{s_1,s_2,\dots ,s_n\}$ in a metric space and an integer $k$, the center selection problem asks to find a subset of $k$ centers $C\subseteq S$ that minimises the maximum distance of any site to its nearest center.

Formally, we seek to minimise the radius $r$:

$$r(C)=\underset{s\in S}{\max }\mathrm{dist}(s,C)$$

where $\mathrm{dist}(s,C)={\min }_{c\in C}\mathrm{dist}(s,c)$.

Complexity and Approximation

The centre selection problem is an NP-hard optimisation problem.

Greedy Approximation

A simple greedy algorithm provides a 2-approximation:

1. Pick an arbitrary site $s\in S$ and add it to $C$.
2. While $|C|<k$:
   • Find the site $s\in S$ that is furthest from the current set $C$(i.e., maximises $\mathrm{dist}(s,C)$).
   • Add this site to $C$.

Optimality of Approximation

Unless $P=NP$, there is no approximation algorithm for the centre selection problem with an approximation factor better than 2.