The K-Centre Problem for Necklaces

Adamson, Duncan, Deligkas, Argyrios, Gusev, Vladimir V and Potapov, Igor
(2020) The K-Centre Problem for Necklaces. [Internet Publication]

[img] Text
2005.10095v1.pdf - Submitted Version

Download (207kB) | Preview


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.

Item Type: Internet Publication
Uncontrolled Keywords: cs.DS, cs.DS
Depositing User: Symplectic Admin
Date Deposited: 06 Jul 2020 11:01
Last Modified: 09 May 2022 21:10
Related URLs: