Strong linear independence in bottleneck algebra

algebraic linear system binary search techniques bottleneck algebra linear bottleneck assignment problem linear independence strong permanent strongly independent columns strongly regular matrix trapezoidal matrix

Mathematics Subject Classification ID

Ordered groups (06F15) Vector spaces, linear dependence, rank, lineability (15A03) Determinants, permanents, traces, other special matrix functions (15A15) Numerical mathematical programming methods (65K05) Analysis of algorithms and problem complexity (68Q25) Deterministic scheduling theory in operations research (90B35) Programming in abstract spaces (90C48)

Review text

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. \textit{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))\).

Recommendations

Cites work

Cited in

(19)

This page was built for publication: Strong linear independence in bottleneck algebra

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1094338)