TY - GEN
T1 - The k-centre problem for classes of cyclic words
AU - Adamson, Duncan
AU - Deligkas, Argyrios
AU - Gusev, Vladimir V.
AU - Potapov, Igor
N1 - Funding: The authors thank the Leverhulme Trust via the Leverhulme Research Centre for Functional Materials Design at the University of Liverpool for their support. Potapov—Partially supported by ESPRC grant (EP/R018472/1).
PY - 2023/1/1
Y1 - 2023/1/1
N2 - The problem of finding k uniformly spaced points (centres) within a metric space is well known as the k-centre selection problem. In this paper, we introduce the challenge of k-centre selection on a class of objects of exponential size and study it for the class of combinatorial necklaces, known as cyclic words. The interest in words under translational symmetry is motivated by various applications in algebra, coding theory, crystal structures and other physical models with periodic boundary conditions. We provide solutions for the centre selection problem for both one-dimensional necklaces and largely unexplored objects in combinatorics on words - multidimensional combinatorial necklaces. The problem is highly non-trivial as even verifying a solution to the k-centre problem for necklaces can not be done in polynomial time relative to the length of the cyclic words and the alphabet size unless P= NP. Despite this challenge, we develop a technique of centre selection for a class of necklaces based on de-Bruijn Sequences and provide the first polynomial O(k· n) time approximation algorithm for selecting k centres in the set of 1D necklaces of length n over an alphabet of size q with an approximation factor of O(1+logq(k·n)/n-logq(k·n)). For the set of multidimensional necklaces of size n1× n2× … × nd we develop an O(k· N2) time algorithm with an approximation factor of O(1+logq(k·N)/N-logq(k·N)) in O(k· N2) time, where N= n1· n2· … · nd by approximating de Bruijn hypertori technique.
AB - The problem of finding k uniformly spaced points (centres) within a metric space is well known as the k-centre selection problem. In this paper, we introduce the challenge of k-centre selection on a class of objects of exponential size and study it for the class of combinatorial necklaces, known as cyclic words. The interest in words under translational symmetry is motivated by various applications in algebra, coding theory, crystal structures and other physical models with periodic boundary conditions. We provide solutions for the centre selection problem for both one-dimensional necklaces and largely unexplored objects in combinatorics on words - multidimensional combinatorial necklaces. The problem is highly non-trivial as even verifying a solution to the k-centre problem for necklaces can not be done in polynomial time relative to the length of the cyclic words and the alphabet size unless P= NP. Despite this challenge, we develop a technique of centre selection for a class of necklaces based on de-Bruijn Sequences and provide the first polynomial O(k· n) time approximation algorithm for selecting k centres in the set of 1D necklaces of length n over an alphabet of size q with an approximation factor of O(1+logq(k·n)/n-logq(k·n)). For the set of multidimensional necklaces of size n1× n2× … × nd we develop an O(k· N2) time algorithm with an approximation factor of O(1+logq(k·N)/N-logq(k·N)) in O(k· N2) time, where N= n1· n2· … · nd by approximating de Bruijn hypertori technique.
UR - https://doi.org/10.1007/978-3-031-23101-8
U2 - 10.1007/978-3-031-23101-8_26
DO - 10.1007/978-3-031-23101-8_26
M3 - Conference contribution
AN - SCOPUS:85146694298
SN - 9783031231001
T3 - Lecture notes in computer science
SP - 385
EP - 400
BT - SOFSEM 2023 - Theory and practice of computer science
A2 - Gąsieniec, Leszek
PB - Springer
CY - Cham
T2 - 48th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2023
Y2 - 15 January 2023 through 18 January 2023
ER -