An \(O(n^{2}\)) algorithm for maximum cycle mean of Monge matrices in max-algebra.
type: Item
instance of: scholarly article
title: An \(O(n^{2}\)) algorithm for maximum cycle mean of Monge matrices in max-algebra.
zbMATH Open document ID: 1041.90045
DOI: 10.1016/S0166-218X(02)00395-5
author: Ján Plavka
author: M. Gavalec
published in: Discrete Applied Mathematics
publication date: 2003-06-10T00:00:00Z
review text: For a \((n\times n)\) real matrix \((a_{ij})\), the known algorithm by \textit{R. M. Karp} [Discrete Math. 23, No. 3, 309--311 (1978; Zbl 0386.05032)] exists to find the maximum cycle mean in \(O(n^3)\) time, i.e. to find \(\max (a_{i_1 i_2}+a_{i_2 i_3}+\ldots +a_{i_p i_1})/p\) over all cyclic permutations \((i_1,\ldots ,i_p)\) of subsets of the set \(\{ 1,2,\ldots,n\}.\) The paper deals with the case when \((a_{ij})\) is a Monge or inverse Monge matrix, i.e. \((a_{ij})\) satisfies the so-called Monge property \(a_{ij}+a_{kl}\leq a_{il}+a_{kj}\) or inverse Monge property \(a_{ij}+a_{kl}\geq a_{il}+a_{kj}\) for all \(1\leq i< k\leq n,\) \( 1\leq j < l \leq n.\) An algorithm of complexity \(O(n^2)\) is proposed to find the maximum cycle mean (eigenvalue).
reviewed by: Svetlana A. Kravchenko
Mathematics Subject Classification ID: 90C27
Mathematics Subject Classification ID: 05B35
Mathematics Subject Classification ID: 05C50
zbMATH DE Number: 1925265
zbMATH Keywords: eigenvalue
zbMATH Keywords: Monge matrix
MaRDI profile type: Publication
cites work: Perspectives of Monge properties in optimization
cites work: An \(O(n^ 2)\) algorithm for the maximum cycle mean of an \(n\times n\) bivalent matrix
cites work: On the Monge property of matrices
cites work: Minimax algebra
cites work: Q5583694
cites work: Q3684177
cites work: A characterization of the minimum cycle mean in a digraph
cites work: Q4130999
cites work: The complexity of finding the minimal of the maximum cycle means of similar zero-one matrices
cites work: Recognition of \(d\)-dimensional Monge arrays
cites work: Linear and combinatorial optimization in ordered algebraic structures
description: scientific article; zbMATH DE number 1925265