We study the optimal placement of replicas of data objects in a connected network with the topology of a straight-line segment. This special case of a NP-complete location problem has a remarkably attractive algebraic solution. The minimum cost problem gives rise to tridiagonal matrices that are both persymmetric and symmetric and these are used to prove the symmetry of the optimal solution. The eigenvalues and eigenvectors of these matrices are completely described by Chebyshev polynomials of the second kind to give a complete solution to the replica location problem. We denote the kth Chebyshev polynomials of the second kind by Uk. The Chebyshev identity U2m+1 = 2(x-1) × ((U0 + U1)2 + (U1+U2)2+ ⋯ +(Um-1 + Um)2) + 2(x+m)arises naturally in examining the norms of the eigenvectors that occur.

Additional Metadata
Keywords Characteristic polynomial, Chebyshev polynomials of the second kind, Location, Replica
Persistent URL dx.doi.org/10.1007/s00200-002-0113-1
Journal Applicable Algebra in Engineering, Communications and Computing
Citation
Pressman, I. (2003). The replica location problem and Chebyshev polynomials of the second kind. Applicable Algebra in Engineering, Communications and Computing, 13(6), 427–436. doi:10.1007/s00200-002-0113-1