An \(O(n^{2}\)) algorithm for maximum cycle mean of Monge matrices in max-algebra. (Q1811083)

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).