Deterministic discrepancy minimization

Nikhil Bansal; Joel Spencer

doi:10.1007/978-3-642-23719-5_35

Deterministic discrepancy minimization

Nikhil Bansal, Joel Spencer

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

We derandomize a recent algorithmic approach due to Bansal [2] to efficiently compute low discrepancy colorings for several problems. In particular, we give an efficient deterministic algorithm for Spencer's six standard deviations result [13], and to a find low discrepancy coloring for a set system with low hereditary discrepancy.

Original language	English (US)
Title of host publication	Algorithms, ESA 2011 - 19th Annual European Symposium, Proceedings
Pages	408-420
Number of pages	13
DOIs	https://doi.org/10.1007/978-3-642-23719-5_35
State	Published - 2011
Event	19th Annual European Symposium on Algorithms, ESA 2011 - Saarbrucken, Germany Duration: Sep 5 2011 → Sep 9 2011

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	6942 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	19th Annual European Symposium on Algorithms, ESA 2011
Country/Territory	Germany
City	Saarbrucken
Period	9/5/11 → 9/9/11

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-642-23719-5_35

Cite this

Deterministic discrepancy minimization. / Bansal, Nikhil; Spencer, Joel.
Algorithms, ESA 2011 - 19th Annual European Symposium, Proceedings. 2011. p. 408-420 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6942 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Bansal, N & Spencer, J 2011, Deterministic discrepancy minimization. in Algorithms, ESA 2011 - 19th Annual European Symposium, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 6942 LNCS, pp. 408-420, 19th Annual European Symposium on Algorithms, ESA 2011, Saarbrucken, Germany, 9/5/11. https://doi.org/10.1007/978-3-642-23719-5_35

@inproceedings{4d16d46f6b5141f0957e29ff540745f1,

title = "Deterministic discrepancy minimization",

abstract = "We derandomize a recent algorithmic approach due to Bansal [2] to efficiently compute low discrepancy colorings for several problems. In particular, we give an efficient deterministic algorithm for Spencer's six standard deviations result [13], and to a find low discrepancy coloring for a set system with low hereditary discrepancy.",

author = "Nikhil Bansal and Joel Spencer",

year = "2011",

doi = "10.1007/978-3-642-23719-5_35",

language = "English (US)",

isbn = "9783642237188",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "408--420",

booktitle = "Algorithms, ESA 2011 - 19th Annual European Symposium, Proceedings",

note = "19th Annual European Symposium on Algorithms, ESA 2011 ; Conference date: 05-09-2011 Through 09-09-2011",

}

TY - GEN

T1 - Deterministic discrepancy minimization

AU - Bansal, Nikhil

AU - Spencer, Joel

PY - 2011

Y1 - 2011

N2 - We derandomize a recent algorithmic approach due to Bansal [2] to efficiently compute low discrepancy colorings for several problems. In particular, we give an efficient deterministic algorithm for Spencer's six standard deviations result [13], and to a find low discrepancy coloring for a set system with low hereditary discrepancy.

AB - We derandomize a recent algorithmic approach due to Bansal [2] to efficiently compute low discrepancy colorings for several problems. In particular, we give an efficient deterministic algorithm for Spencer's six standard deviations result [13], and to a find low discrepancy coloring for a set system with low hereditary discrepancy.

UR - http://www.scopus.com/inward/record.url?scp=80052802393&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=80052802393&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-23719-5_35

DO - 10.1007/978-3-642-23719-5_35

M3 - Conference contribution

AN - SCOPUS:80052802393

SN - 9783642237188

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 408

EP - 420

BT - Algorithms, ESA 2011 - 19th Annual European Symposium, Proceedings

T2 - 19th Annual European Symposium on Algorithms, ESA 2011

Y2 - 5 September 2011 through 9 September 2011

ER -

Deterministic discrepancy minimization

Abstract

Publication series

Other

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this