Strong regularity of matrices -- a survey of results
type: Item
instance of: scholarly article
title: Strong regularity of matrices -- a survey of results
zbMATH Open document ID: 0804.06017
DOI: 10.1016/0166-218X(92)00104-T
published in: Discrete Applied Mathematics
publication date: 1995-01-03T00:00:00Z
review text: Let \((G,\otimes,\leq)\) be a linearly ordered commutative group and define an addition by \(x\oplus y= \max(x,y)\) for all \(x,y\in G\). Both operations extend in a canonical way to addition and multiplication of matrices over \(G\). If the linear system \(A\otimes x= b\) has a unique solution \(x\in G^ n\) for some \(b\in G^ m\), then the columns of the \(m\times n\) matrix \(A\) are called \textit{strongly linearly independent (SLI)}. In particular, if \(m= n\), then such a matrix \(A\) is called \textit{strongly regular (SR)}. The survey describes characterizations of strong linear independence and strong regularity. Strong regularity can be checked in \(O(n^ 3)\) using certain combinatorial algorithms. No polynomial time algorithm is known to testify strong linear independence. A similar discussion is done for monoids \((B,\otimes,\leq)\) with \(a\otimes b:=\min(a,b)\) for all \(a,b{\i}B\), which are based on some underlying linearly ordered set \((B,\leq)\). Here, for dense sets, efficient tests for \(SLI\) (in \(O(mn\log n))\) as well as \(SR\) (in \(O(n^ 2\log n))\) are known, while the general case remains open. In both systems the permanent is the value of the corresponding (sum or bottleneck) assignment problem. Unique solvability of the assignment problem is closely related to strong regularity. Bottleneck assignment problems with unique optimum can be solved in \(O(n^ 2\log n)\), i.e. faster than in the general case for which an \(O(n^{2.5}\sqrt{\log n})\) algorithm is known. A similar improvement is not known for sum assignment problems.
Mathematics Subject Classification ID: 06F25
Mathematics Subject Classification ID: 90C27
Mathematics Subject Classification ID: 90C60
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 501149
zbMATH Keywords: max-algebra
zbMATH Keywords: bottleneck algebra
zbMATH Keywords: matrix operations
zbMATH Keywords: survey
zbMATH Keywords: strong linear independence
zbMATH Keywords: strong regularity
zbMATH Keywords: combinatorial algorithms
zbMATH Keywords: monoids
zbMATH Keywords: assignment problem
author: Peter Butkovič
reviewed by: Uwe T. Zimmermann
MaRDI profile type: Publication
cites work: Strong linear independence in bottleneck algebra
cites work: On the regularity of matrices in min algebra
cites work: An \(O(n^ 2)\) algorithm for the maximum cycle mean of an \(n\times n\) bivalent matrix
cites work: A condition for the strong regularity of matrices in the minimax algebra
cites work: Strong regularity of matrices in a discrete bottleneck algebra
cites work: On the powers of matrices in bottleneck/fuzzy algebra
cites work: Q3964346
cites work: Maximum cycle-means of weighted digraphs
cites work: Algorithms for two bottleneck optimization problems
cites work: A characterization of the minimum cycle mean in a digraph
cites work: Q4739657
cites work: Q3880617
cites work: Linear and combinatorial optimization in ordered algebraic structures
description: scientific article; zbMATH DE number 501149