An O(n^2) algorithm for maximum cycle mean of Monge matrices in max-algebra.
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).
- Special properties of Monge matrices in max-plus algebra
- Structure of the eigenspace of a Monge matrix in max-plus algebra
- An O(n^ 2) algorithm for the maximum cycle mean of an n n bivalent matrix
- An iterative algorithm for computing the cycle mean of a Toeplitz matrix in special form
- Structure and dimension of the eigenspace of a concave Monge matrix
- A characterization of the minimum cycle mean in a digraph
- An O(n^ 2) algorithm for the maximum cycle mean of an n n bivalent matrix
- scientific article; zbMATH DE number 3906559 (Why is no real title available?)
- scientific article; zbMATH DE number 3558962 (Why is no real title available?)
- scientific article; zbMATH DE number 3302125 (Why is no real title available?)
- Linear and combinatorial optimization in ordered algebraic structures
- Minimax algebra
- On the Monge property of matrices
- Perspectives of Monge properties in optimization
- Recognition of \(d\)-dimensional Monge arrays
- The complexity of finding the minimal of the maximum cycle means of similar zero-one matrices
- Structure and dimension of the eigenspace of a concave Monge matrix
- An O(n^ 2) algorithm for the maximum cycle mean of an n n bivalent matrix
- On the recognition of permuted bottleneck Monge matrices
- Fast distance multiplication of unit-Monge matrices
- Computing an eigenvector of a Monge matrix in max-plus algebra
- Structure of the eigenspace of a Monge matrix in max-plus algebra
- \(\ell\)-parametric eigenproblem in max-algebra
- Special properties of Monge matrices in max-plus algebra
- An iterative algorithm for computing the cycle mean of a Toeplitz matrix in special form
- Eigenproblem for optimal-node matrices in max-plus algebra
- Computation of the second maximum path weight in a max-plus matrix
- scientific article; zbMATH DE number 3965044 (Why is no real title available?)
- 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
- Eigenproblem for monotone and toeplitz matrices in a Max-algebra
- The complexity of finding the minimal of the maximum cycle means of similar zero-one matrices
- Tropical Vandermonde matrices
- Fast distance multiplication of unit-Monge matrices
- Static maxium cycle mean problem of a trivalent matrix
- Computing an eigenvector of an inverse Monge matrix in max-plus algebra
- On the \(\lambda \)-robustness of matrices over fuzzy algebra
- A similarity canonical form for max-plus matrices and its eigenproblem
- On the Monge property of matrices
This page was built for publication: An \(O(n^{2}\)) algorithm for maximum cycle mean of Monge matrices in max-algebra.
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1811083)
