TheO(n3) algorithm for a special case of the maximum cost-to-time ratio cycle problem and its coherence with an eigenproblem of a matrix期刊界 All Journals 搜尽天下杂志传播学术成果专业期刊搜索期刊信息化学术搜索

TheO(n3) algorithm for a special case of the maximum cost-to-time ratio cycle problem and its coherence with an eigenproblem of a matrix

Authors:	J. Plávka

Affiliation:	(1) Department of Mathematics, Technical University, Zbrojnicná 3, 04001 Koice, Czechoslovakia

Abstract:	Let twon×n matrices be given, namely a real matrixA=(a_ij) and a (0, 1)-matrixT=(t_ij). For a cyclic permutation=(i₁,i₂,...,i_k) of a subset of N={1, 2, ..., n} we define _A;T(), the cost-to-time ratio weight of, as $(a_{i_1 i_2 } + cdots + a_{i_k i_1 } )/(t_{i_1 i_2 } + cdots + t_{i_k i_1 } )$ . This paper presents an O(n³) algorithm for finding (A;T)=max _A;T(), the maximum cost-to-time ratio weight of the matricesA andT. Moreover a generalised eigenproblem is proposed.

Keywords:	matrices ratio cycle weight graph theory
本文献已被 SpringerLink 等数据库收录！