Abstract
Let twon×n matrices be given, namely a real matrixA=(aij) and a (0, 1)-matrixT=(tij). For a cyclic permutationσ=(i 1,i 2,...,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(n3) 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.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Cuninghame-Green RA (1979) Minimax algebra, Lecture notes in economics and mathematical systems 166, Springer, Berlin
Dantzig GB, Blattner W (1967) Finding a cycle in a graph with minimum cost-to-time ratio with application to a shiprouting problem, in: P Rosentiehl, ed., Theory of Graphs Dunod, Paris: 77-84
Karp RM (1978) A characterization of the minimum cycle mean in a digraph. Discrete Math. 23:309–311
Lawler EL (1976) Combinatorial optimization: Network and Matroids Holt, Rinehart and Winston, New York
Noltemeier H (1976) Graphentheorie mit Algorithmen and Anwendungen, Berlin, Walter de Gruyter
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Plávka, J. 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. ZOR - Methods and Models of Operations Research 36, 417–422 (1992). https://doi.org/10.1007/BF01415758
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01415758