An efficient string sorting algorithm for weighing matrices of small weight |
| |
Authors: | Ilias S Kotsireas Christos Koukouvinos Panos M Pardalos |
| |
Institution: | 1.Department of Physics and Computer Science,Wilfrid Laurier University,Waterloo,Canada;2.Department of Mathematics,National Technical University of Athens,Zografou, Athens,Greece;3.Department of Industrial and Systems Engineering,University of Florida,Gainesville,USA |
| |
Abstract: | In this paper, we demonstrate that the search for weighing matrices of small weights constructed from two circulants can be
viewed as a string sorting problem together with a linear time algorithm to locate common strings in two sorted arrays. We
also introduce a sparse encoding of the periodic autocorrelation function vector, based on concepts from Algorithmic Information
Theory, also known as Kolmogorov complexity, that allows us to speed up the algorithm considerably. Finally, we use these
ideas to find new weighing matrices W(2 · n, 9) constructed from two circulants, for many values of n in the range 100 ≤ n ≤ 300. These matrices are given here for the first time. We also discuss briefly a connection with Combinatorial Optimization. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|