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

MSC:
 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:
References:
  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  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  Butkovič, P.; Szabó, P., An algorithm for checking strong regularity of matrices in the bottleneck algebra, (), to appear.  Cechlárová, K., On some properties of the algebraic assignment problem, Ekonom.- mat. obzor, 22, 462-467, (1986) · Zbl 0607.90090  Chvátal, V., (), 344  Cuninghame-Green, R.A., Minimax algebra, Lecture notes in econom. and math. systems., 166, (1979), Springer Berlin · Zbl 0399.90052  Knuth, D.E., (), 149  Papadimitriou, C.H.; Steiglitz, K., (), 24  Zimmermann, K., Extremální algebra, (1976), Ekonom. ústav ČSAV Praha, (in Czech)  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.