论文标题
项链的K-Centre问题
The K-Centre Problem for Necklaces
论文作者
论文摘要
在图理论中，K-Centre问题的目的是找到一组$ k $的顶点，其中任何顶点的最大距离与$ k $ set中最接近的顶点的最大距离被最小化。在本文中，我们介绍了一组项链的$ k $ - 中心问题，即循环移位下的单词等效类别。这可以看作是完整加权图上的K-中心问题，其中每条项链都由顶点表示，并且每个边缘的权重由任何一对项链之间的重叠距离给出。与图形案例类似，目标是选择$ k $项链，以便将语言及其最近中心的任何单词的距离最小化。但是，在语言的K-Centre问题的情况下，相关图的大小可能与语言的描述有关，即单词l的长度和字母q的大小。我们在项链上的$ k $中心问题得出了几种近似算法，在L和K的上下文中具有对数近似因子，并且在更限制的情况下的恒定因素内。
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.
