The k-Centre Problem for Classes of Cyclic Words

Adamson, Duncan ORCID: 0000-0003-3343-2435, Deligkas, Argyrios, Gusev, Vladimir V and Potapov, Igor (2023) The k-Centre Problem for Classes of Cyclic Words .

Access the full-text of this item by clicking on the Open Access link.

PDF paper_5675 (3).pdf - Author Accepted Manuscript Download (2MB) | Preview

Abstract

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 n<inf>1</inf>× n<inf>2</inf>× … × n<inf>d</inf> we develop an O(k· N²) time algorithm with an approximation factor of O(1+logq(k·N)N-logq(k·N)) in O(k· N²) time, where N= n<inf>1</inf>· n<inf>2</inf>· … · n<inf>d</inf> by approximating de Bruijn hypertori technique.

Item Type:	Conference Item (Unspecified)
Uncontrolled Keywords:	46 Information and Computing Sciences
Divisions:	Faculty of Science & Engineering > School of Electrical Engineering, Electronics and Computer Science Faculty of Science & Engineering > School of Physical Sciences
Depositing User:	Symplectic Admin
Date Deposited:	24 May 2023 08:13
Last Modified:	23 May 2026 07:11
DOI:	10.1007/978-3-031-23101-8_26
Open Access URL:	https://doi.org/10.48550/arXiv.2005.10095
Related Websites:	Author Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3170611
Disclaimer:	The University of Liverpool is not responsible for content contained on other websites from links within repository metadata. Please contact us if you notice anything that appears incorrect or inappropriate.