zbMATH — the first resource for mathematics

Strong linear independence in bottleneck algebra. (English) Zbl 0629.90093
Linear systems of the form \[ \max_{1\leq j\leq n}\min (a_{ij},x_ j)=b_ i\quad (1\leq i\leq m) \] have been treated in the literature for a long time [e.g. cf. K. Zimmermann [Extremalni algebra, Praha: Vyzkumná publicace Ekonomicko-matematické Laboratorie pri Ekonomickém ústava CSAV 46, 127 p. (1976)] or the reviewer [Linear and combinatorial optimization in ordered algebraic structures (1981; Zbl 0466.90045)]. Here, all coefficients \(a_{ij}\), \(b_ i\) are chosen from a dense, linearly ordered set (B,\(\leq)\). If the linear system is uniquely solvable for some \(b\in B^ m\) the columns in the matrix \(A=(a_{ij})\) are called strongly linearly independent. Square matrices with strongly independent columns are called strongly regular. An \(m\times n\) matrix A has SLI-columns if and only if it contains a strongly regular matrix of size n. The matrix A is called trapezoidal, if \(a_{kk}>\max \{a_{j}| \quad 1\leq i\leq k,\quad i<j\leq n\}\) for all \(1\leq k\leq m\). It is proved that every strongly regular matrix A can be transformed into a trapezoidal matrix by suitable row- and column- permutations. Vice versa, every trapezoidal matrix is strongly regular. For the latter result, density of B is a necessary assumption. An O(m\(\cdot n\cdot \log (n))\)-algorithm is developed which constructs the row- and column-permutations revealing a hidden trapezoidal matrix. It is well-known that the linear bottleneck assignment problem \(\max_{\pi \in S}\min \{a_{i\pi (i)}| \quad 1\leq i\leq n\},\) where S denotes the set of all permutations of \(\{\) 1,2,...,n\(\}\), can be solved in \(O(n^{5/2}\cdot \log (n))\) using binary search techniques. If A is trapezoidal, then the identity is optimal. If the linear bottleneck assignment problem has a unique optimal solution then A is proved to be strongly regular and, therefore, by revealing its hidden trapezoidal form, the linear bottleneck problem can be solved in \(O(n^ 2\cdot \log (n))\).
Reviewer: U.Zimmermann

90C48 Programming in abstract spaces
90B35 Deterministic scheduling theory in operations research
68Q25 Analysis of algorithms and problem complexity
15A03 Vector spaces, linear dependence, rank, lineability
65F30 Other matrix algorithms (MSC2010)
06F15 Ordered groups
15A15 Determinants, permanents, traces, other special matrix functions
65K05 Numerical mathematical programming methods
Zbl 0466.90045
Full Text: DOI
[1] Burkard, R.E.; Zimmermann, U., Weakly admissible transformations for solving algebraic assignment and transportation problems, Math. programming stud., 12, 1-18, (1980) · Zbl 0435.90108
[2] 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
[3] Butkovič, P.; Szabó, P., An algorithm for checking strong regularity of matrices in the bottleneck algebra, (), to appear.
[4] Cechlárová, K., On some properties of the algebraic assignment problem, Ekonom.- mat. obzor, 22, 462-467, (1986) · Zbl 0607.90090
[5] Chvátal, V., (), 344
[6] Cuninghame-Green, R.A., Minimax algebra, Lecture notes in econom. and math. systems., 166, (1979), Springer Berlin · Zbl 0399.90052
[7] Knuth, D.E., (), 149
[8] Papadimitriou, C.H.; Steiglitz, K., (), 24
[9] Zimmermann, K., Extremální algebra, (1976), Ekonom. ústav ČSAV Praha, (in Czech)
[10] Zimmermann, U., Linear and combinatorial optimization in ordered algebraic structures, Ann. discrete math., No. 10, (1981), North Holland Amsterdam · 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.