Linear discrepancy of basic totally unimodular matrices (Q1583619)

From MaRDI portal





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
    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

    Identifiers