  In graph theory, the objective of the k-centre problem is to find a set of
$k$ vertices for which the largest distance of any vertex to its closest vertex
in the $k$-set is minimised. In this paper, we introduce the $k$-centre problem
for sets of necklaces, i.e. the equivalence classes of words under the cyclic
shift. This can be seen as the k-centre problem on the complete weighted graph
where every necklace is represented by a vertex, and each edge has a weight
given by the overlap distance between any pair of necklaces. Similar to the
graph case, the goal is to choose $k$ necklaces such that the distance from any
word in the language and its nearest centre is minimised. However, in a case of
k-centre problem for languages the size of associated graph maybe exponential
in relation to the description of the language, i.e., the length of the words l
and the size of the alphabet q. We derive several approximation algorithms for
the $k$-centre problem on necklaces, with logarithmic approximation factor in
the context of l and k, and within a constant factor for a more restricted
case.
