@inproceedings{bf7c78b24d2849b8b001f94fdc945d44,
title = "Lattice approximation and linear discrepency of totally unimodular matrices",
abstract = "This paper shows that the lattice approximation problem for totally unimodular matrices A □ Rm×n can be solved efficiently and optimally via a linear programming approach. The complexity of our algorithm is \&Ogr;(log m) times the complexity of finding an extremal point of a polytope in Rn described by 2(m + n) linear constraints. We also consider the worst-case approximability. This quantity is usually called linear discrepancy lindisc(/4). For any totally unimodular m × n matrix A we show lindisc(4) ≤ min\{1 - 1/n+1, 1 - 1/m\}. This bound is sharp. It proves Spencer's conjecture lindisc(A) ≤ (1 - 1/n+1) herdisc(4) for totally unimodular matrices. This seems to be the first time that linear programming is successfully used for a discrepancy problem.",
keywords = "Algorithms, Theory, Verification",
author = "Benjamin Doerr",
year = "2001",
month = dec,
day = "1",
language = "English",
isbn = "0898714907",
series = "Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms",
pages = "119--125",
booktitle = "Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms",
note = "2001 Operating Section Proceedings, American Gas Association ; Conference date: 30-04-2001 Through 01-05-2001",
}