在图论中，k-中心问题的目标是找到一组 k 顶点，其中任何点与其在K-集合中距其最近的点的最大距离最小化。在本文中，我们介绍了项链集的k-中心问题，即循环移位下词的等价类。这可以被看作是完整加权图上的 k-中心问题，其中每个项链都由点表示，并且每个边都含有一个权重：由每一对项链的重叠距离决定。与图例相似的是，目标是选择 k个项链，就可以类比成将语句中任何单词与其最近的中心之间的距离降至最低。但是，当k-中心问题与语言相关时，产生图的大小可能是相对于语言描述呈指数化趋势。举个例子来说，单词 l 的长度和字母 q 的大小。我们针对项链上的 k-中心问题推导出多个近似算法，在 l 和 k 上下文中具有对数级的近似因子，并且在更局限的情况下包含于恒定因子内。

原文标题：The K-Centre Problem for Necklaces

原文：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.

原文作者：Duncan Adamson, Argyrios Deligkas, Vladimir V. Gusev, Igor Potapov

原文地址：http://arxiv.org/abs/2005.10095