Linear discrepancy of basic totally unimodular matrices (Q1583619)
From MaRDI portal
![]() | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Linear discrepancy of basic totally unimodular matrices |
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Linear discrepancy of basic totally unimodular matrices |
scientific article |
Statements
Linear discrepancy of basic totally unimodular matrices (English)
0 references
30 November 2000
0 references
The linear discrepancy of an \(m\times n\) - matrix \(A\) is defined by \[ \text{lindisc} (A):= \max_{p\in[0,1]^n} \min_{\chi\in\{0,1\}^n} \|A(p-\chi)\|_\infty . \] A matrix \(A\) is called totally unimodular if the determinant of each square submatrix is \(-1, 0, 1\). The authors show that the linear discrepancy of a basic totally unimodular matrix \(A\) is at most \(1-\frac{1}{n+1}\), extending a result of \textit{H. Peng} and \textit{C. H. Yan} [Discrete Math. 219, 223-233 (2000; Zbl 0951.05016)].
0 references
totally unimodular matrices
0 references
0-1-matrices
0 references
linear discrepancy
0 references
determinant
0 references