zbMATH — the first resource for mathematics

Strong regularity of matrices – a survey of results. (English) Zbl 0804.06017
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 strongly linearly independent (SLI). In particular, if \(m= n\), then such a matrix \(A\) is called 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.

06F25 Ordered rings, algebras, modules
90C27 Combinatorial optimization
90C60 Abstract computational complexity for mathematical programming problems
68Q25 Analysis of algorithms and problem complexity
Full Text: DOI
[1] Butkovič, P.; Cechlárová, K.; Szabó, P., Strong linear independence in bottleneck algebra, Linear algebra appl., 94, 133-155, (1987) · Zbl 0629.90093
[2] Butkovič, P.; Cuninghame-Green, R.A., On the regularity of matrices in MIN algebra, Linear algebra appl., 145, 127-139, (1991) · Zbl 0731.15012
[3] Butkovič, P.; Cuninghame-Green, R.A., An O(n2) algorithm for the maximum cycle Mean of an n × n bivalent matrix, Discrete appl. math., 35, 157-162, (1992) · Zbl 0776.05070
[4] Butkovič, P.; Hevery, F., A condition for the strong regularity of matrices in the minimax algebra, Discrete appl. math., 11, 209-222, (1985) · Zbl 0602.90136
[5] Butkovič, P.; Szabó, P., An algorithm for checking the strong regularity of matrices in the bottleneck algebra, ()
[6] Cechlárová, K., Strong regularity of matrices in a discrete bottleneck algebra, Linear algebra appl., 128, 35-50, (1990) · Zbl 0704.15003
[7] Cechlárová, K., Matrices in the bottleneck algebra, () · Zbl 0866.15009
[8] Cuninghame-Green, R.A., Describing industrial processes with interference and approximating their steady-state behaviour, Oper. res. quart., 13, 95-100, (1962)
[9] Cuninghame-Green, R.A., Minimax algebra, () · Zbl 0498.90084
[10] Cuninghame-Green, R.A.; Lin, Y., Maximum cycle-means of weighted digraphs, () · Zbl 0854.68076
[11] Gabow, H.N.; Tarjan, R.E., Algorithms for two bottleneck optimization problems, Algorithms, 9, 411-417, (1988) · Zbl 0653.90087
[12] Karp, R.M., A characterization of the minimum cycle Mean in a digraph, Discrete math., 23, 309-311, (1978) · Zbl 0386.05032
[13] Papadimitriou, C.H.; Steiglitz, K., Combinatorial optimization — algorithms and complexity, (1982), Prentice-Hall Englewood Cliffs, NJ · Zbl 0503.90060
[14] Vorobyev, N.N., Extremal algebra of positive matrices, Elektron. informationsverarbeitung und kybernetik, 3, (1967), (in Russian)
[15] Zimmermann, K., Extremal algebra, (1976), Ekonomický ústav ČSAV Praha, (in Czech) · Zbl 0438.90102
[16] Zimmermann, U., Linear and combinatorial optimization in ordered algebraic structures, () · Zbl 0466.90045
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.