Centre Selection Problem

computation algorithms optimisation

Definition

Center Selection Problem

Given a set of sites in a metric space and an integer , the center selection problem asks to find a subset of centers that minimises the maximum distance of any site to its nearest center.

Formally, we seek to minimise the radius :

where .

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 and add it to .
2. While :
   • Find the site that is furthest from the current set (i.e., maximises ).
   • Add this site to .

Optimality of Approximation

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