BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//University of Liverpool Computer Science Seminar System//v2//EN
BEGIN:VEVENT
DTSTAMP:20260416T202331Z
UID:Seminar-ACTO-1018@lxserverM.csc.liv.ac.uk
ORGANIZER:CN=Nikhil Mande:MAILTO:Nikhil.Mande@liverpool
DTSTART:20220914T140000
DTEND:20220914T150000
SUMMARY:Algorithms, Complexity Theory and Optimisation Series
DESCRIPTION:Duncan Adamson: The k-center Problem for Classes of Cyclic Words\n\nThe problem of finding k uniformly spaced points (centres) within a metric space is well known as the k-centre selection problem. We introduce a 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 cannot 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 \cdot 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 + \frac{\log_q(k \cdot n)}{n - \log_q(k \cdot n)}). For the set of multidimensional necklaces of size n_1 n_2 ... n_d we develop an O(k \cdot N^2) time algorithm with an approximation factor of O(1 + \frac{\log_q(k \cdot N)}{N - \log_q(k \cdot N)})$ in O(k \cdot N^2) time, where N = n_1 n_2 ... n_d by approximating de Bruijn hypertori technique\n\nhttps://www.csc.liv.ac.uk/research/seminars/abstract.php?id=1018
LOCATION:208 Ashton Building
END:VEVENT
END:VCALENDAR