00-29   Berichtsreihe des Mathematischen Seminars der Universität Kiel

Benjamin Doerr:

Lattice Approximation and Linear Discrepancy of Totally Unimodular Matrices

This paper shows that the lattice approximation problem for totally unimodular matrices $A \in \R^{m \times n}$ can be solved efficiently and optimally via a linear programming approach. The complexity of our algorithm is $\OO(\log m)$ times the complexity of finding an extremal point of a polytope in $\R^n$ described by $2(m+n)$ linear constraints. We also consider the worst-case approximability. This quantity is usually called linear discrepancy $\lindisc(A)$. For any totally unimodular $m \times n$ matrix $A$ we show $$\lindisc(A) \le \min\{1 - \tfrac 1 {n+1}, 1 - \tfrac 1 m\}.$$ This bound is sharp. It proves Spencer's conjecture $\lindisc(A) \le (1 - \tfrac 1 {n+1})\herdisc(A)$ for totally unimodular matrices. This seems to be the first time that linear programming is successfully used for a discrepancy problem.

Mathematics Subject Classification (1991): 11K38, 90C10

Bibliographical note: Combinatorica 24 (2004), 117-125.

Keywords: Linear programming, totally unimodular matrices, linear discrepancy, lattice approximation

Mail an Jens Burmeister
[Thu Feb 19 18:56:35 2009]
Impressum