Linear and Hereditary Discrepancy

Benjamin Doerr

doi:10.1017/S0963548300004272

Linear and Hereditary Discrepancy

Benjamin Doerr

Christian-Albrechts-University Kiel

Résultats de recherche: Contribution à un journal › Article › Revue par des pairs

Résumé

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.

langue originale	Anglais
Pages (de - à)	349-354
Nombre de pages	6
journal	Combinatorics Probability and Computing
Volume	9
Numéro de publication	4
Les DOIs	https://doi.org/10.1017/S0963548300004272
état	Publié - 1 janv. 2000
Modification externe	Oui

Accès au document

10.1017/S0963548300004272

Contient cette citation

@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

Résumé

Accès au document

Empreinte digitale

Contient cette citation