Linear and Hereditary Discrepancy

Benjamin Doerr

doi:10.1017/S0963548300004272

Linear and Hereditary Discrepancy

Benjamin Doerr

Christian-Albrechts-University Kiel

Research output: Contribution to journal › Article › peer-review

Abstract

Let A be an m x n matrix and q := [log₂(m)] + 1. In this article we improve the well-known bound lindisc(A) ≤ 2 herdisc(A) and show that lindisc(A) ≤ 2 (1 - 2^-q) herdisc(A) (≤ 2 (1 - 1/2m)herdisc(A)). As with the previous proofs relating to this problem, ours is constructive. We will give an on-line algorithm and analyse it using game theory.

Original language	English
Pages (from-to)	349-354
Number of pages	6
Journal	Combinatorics Probability and Computing
Volume	9
Issue number	4
DOIs	https://doi.org/10.1017/S0963548300004272
Publication status	Published - 1 Jan 2000
Externally published	Yes

Access to Document

10.1017/S0963548300004272

Cite this

@article{966d15a8d6a5407db390845be0dc2f8c,

title = "Linear and Hereditary Discrepancy",

abstract = "Let A be an m x n matrix and q := [log2(m)] + 1. In this article we improve the well-known bound lindisc(A) ≤ 2 herdisc(A) and show that lindisc(A) ≤ 2 (1 - 2-q) herdisc(A) (≤ 2 (1 - 1/2m)herdisc(A)). As with the previous proofs relating to this problem, ours is constructive. We will give an on-line algorithm and analyse it using game theory.",

author = "Benjamin Doerr",

year = "2000",

month = jan,

day = "1",

doi = "10.1017/S0963548300004272",

language = "English",

volume = "9",

pages = "349--354",

journal = "Combinatorics Probability and Computing",

issn = "0963-5483",

number = "4",

}

TY - JOUR

T1 - Linear and Hereditary Discrepancy

AU - Doerr, Benjamin

PY - 2000/1/1

Y1 - 2000/1/1

N2 - Let A be an m x n matrix and q := [log2(m)] + 1. In this article we improve the well-known bound lindisc(A) ≤ 2 herdisc(A) and show that lindisc(A) ≤ 2 (1 - 2-q) herdisc(A) (≤ 2 (1 - 1/2m)herdisc(A)). As with the previous proofs relating to this problem, ours is constructive. We will give an on-line algorithm and analyse it using game theory.

AB - Let A be an m x n matrix and q := [log2(m)] + 1. In this article we improve the well-known bound lindisc(A) ≤ 2 herdisc(A) and show that lindisc(A) ≤ 2 (1 - 2-q) herdisc(A) (≤ 2 (1 - 1/2m)herdisc(A)). As with the previous proofs relating to this problem, ours is constructive. We will give an on-line algorithm and analyse it using game theory.

U2 - 10.1017/S0963548300004272

DO - 10.1017/S0963548300004272

M3 - Article

AN - SCOPUS:0034415549

SN - 0963-5483

VL - 9

SP - 349

EP - 354

JO - Combinatorics Probability and Computing

JF - Combinatorics Probability and Computing

IS - 4

ER -

Linear and Hereditary Discrepancy

Abstract

Access to Document

Fingerprint

Cite this