98-34   Berichtsreihe des Mathematischen Seminars der Universität Kiel

Benjamin Doerr:

Linear and hereditary discrepancy

Let $A$ be an $m \times n$ matrix and $q:=\lfloor \log_2(m) \rfloor +1$. In this article we improve the well-known bound $\lindisc(A) \le 2 \herdisc(A)$ and show $$\lindisc(A) \le \c \herdisc(A) \quad \left( \le 2 (1 - \tfrac{1}{2m}) \herdisc(A) \right).$$

As with the previous proofs relating to this problem, ours is constructive. We will give an on-line algorithm and analyze it using game theory.

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

Bibliographical note: Combinatorics, Probability and Computing 9 (2000), 349-354.

Keywords: linear discrepancy, hereditary discrepancy, on-line algorithm, game theory

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