COST-TO-TIME RATIO PROBLEM FOR (0,1)-MATRICES, MONGE-MATRICES AND CIRCULANT MATRICES

Let two nxn matrices be given, namely matrices A = (a(ij)) and T = (t( ij)). For a cyclic permutation sigma = (i(1), i(2),..., i(k)) of a sub set of N = {1, 2,..., n} we define mu(A;T) (sigma), the cost-to-time r atio weight of sigma, as (a(i1i2)+...+a(iki1))/(t(i1i2)+...+t(iki1)). This paper presents procedures for finding lambda(A; T) = max(sigma)mu (A;T)(sigma), the maximum cost-to-time ratio weight of the matrices A and T for cases when A, T be (0, 1)- matrices and A be Monge resp. cir culant matrix, T with 1-entries.