The replica location problem and Chebyshev polynomials of the second kind
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.
|Keywords||Characteristic polynomial, Chebyshev polynomials of the second kind, Location, Replica|
|Journal||Applicable Algebra in Engineering, Communications and Computing|
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