Approximation of multi-color discrepancy

Benjamin Doerr; Anand Srivastav

doi:10.1007/978-3-540-48413-4_5

Approximation of multi-color discrepancy

Benjamin Doerr
, Anand Srivastav

Christian-Albrechts-University Kiel

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

10 Citations (Scopus)

Abstract

In this article we introduce (combinatorial) multi-color discrepancy and generalize some classical results from 2-color discrepancy theory to c colors. We give a recursive method that constructs c-colorings from approximations to the 2-color discrepancy. This method works for a large class of theorems like the six-standard-deviation theorem of Spencer, the Beck-Fiala theorem and the results of Matoušek, Welzl and Wernisch for bounded VC-dimension. On the other hand there are examples showing that discrepancy in c colors can not be bounded in terms of two-color discrepancy even if c is a power of 2. For the linear discrepancy version of the Beck-Fiala theorem the recursive approach also fails. Here we extend the method of oating colors to multi-colorings and prove multi-color versions of the the Beck-Fiala theorem and the Barany-Grunberg theorem.

Original language	English
Title of host publication	Randomization, Approximation, and Combinatorial Optimization
Subtitle of host publication	Algorithms and Techniques - 3rd International Workshop on Randomization and Approximation Techniques in Computer Science and 2nd International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, RANDOM-APPROX 1999, Proceedings
Editors	Jose D. P. Rolim, Alistair Sinclair, Dorit Hochbaum, Klaus Jansen
Publisher	Springer Verlag
Pages	39-50
Number of pages	12
ISBN (Print)	3540663290, 9783540663294
DOIs	https://doi.org/10.1007/978-3-540-48413-4_5
Publication status	Published - 1 Jan 1999
Externally published	Yes
Event	3rd International Workshop on Randomization and Approximation Techniques in Computer Science and 2nd International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, RANDOM-APPROX 1999 - Berkeley, United States Duration: 8 Aug 1999 → 11 Aug 1999

Publication series

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

Conference

Conference	3rd International Workshop on Randomization and Approximation Techniques in Computer Science and 2nd International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, RANDOM-APPROX 1999
Country/Territory	United States
City	Berkeley
Period	8/08/99 → 11/08/99

Access to Document

10.1007/978-3-540-48413-4_5

Cite this

Doerr, B., & Srivastav, A. (1999). Approximation of multi-color discrepancy. In J. D. P. Rolim, A. Sinclair, D. Hochbaum, & K. Jansen (Eds.), Randomization, Approximation, and Combinatorial Optimization: Algorithms and Techniques - 3rd International Workshop on Randomization and Approximation Techniques in Computer Science and 2nd International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, RANDOM-APPROX 1999, Proceedings (pp. 39-50). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1671). Springer Verlag. https://doi.org/10.1007/978-3-540-48413-4_5

Doerr, Benjamin ; Srivastav, Anand. / Approximation of multi-color discrepancy. Randomization, Approximation, and Combinatorial Optimization: Algorithms and Techniques - 3rd International Workshop on Randomization and Approximation Techniques in Computer Science and 2nd International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, RANDOM-APPROX 1999, Proceedings. editor / Jose D. P. Rolim ; Alistair Sinclair ; Dorit Hochbaum ; Klaus Jansen. Springer Verlag, 1999. pp. 39-50 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{361d6ab4f4a6485495b770b596b41314,

title = "Approximation of multi-color discrepancy",

abstract = "In this article we introduce (combinatorial) multi-color discrepancy and generalize some classical results from 2-color discrepancy theory to c colors. We give a recursive method that constructs c-colorings from approximations to the 2-color discrepancy. This method works for a large class of theorems like the six-standard-deviation theorem of Spencer, the Beck-Fiala theorem and the results of Matou{\v s}ek, Welzl and Wernisch for bounded VC-dimension. On the other hand there are examples showing that discrepancy in c colors can not be bounded in terms of two-color discrepancy even if c is a power of 2. For the linear discrepancy version of the Beck-Fiala theorem the recursive approach also fails. Here we extend the method of oating colors to multi-colorings and prove multi-color versions of the the Beck-Fiala theorem and the Barany-Grunberg theorem.",

author = "Benjamin Doerr and Anand Srivastav",

note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 1999.; 3rd International Workshop on Randomization and Approximation Techniques in Computer Science and 2nd International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, RANDOM-APPROX 1999 ; Conference date: 08-08-1999 Through 11-08-1999",

year = "1999",

month = jan,

day = "1",

doi = "10.1007/978-3-540-48413-4\_5",

language = "English",

isbn = "3540663290",

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

publisher = "Springer Verlag",

pages = "39--50",

editor = "Rolim, \{Jose D. P.\} and Alistair Sinclair and Dorit Hochbaum and Klaus Jansen",

booktitle = "Randomization, Approximation, and Combinatorial Optimization",

}

Doerr, B & Srivastav, A 1999, Approximation of multi-color discrepancy. in JDP Rolim, A Sinclair, D Hochbaum & K Jansen (eds), Randomization, Approximation, and Combinatorial Optimization: Algorithms and Techniques - 3rd International Workshop on Randomization and Approximation Techniques in Computer Science and 2nd International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, RANDOM-APPROX 1999, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 1671, Springer Verlag, pp. 39-50, 3rd International Workshop on Randomization and Approximation Techniques in Computer Science and 2nd International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, RANDOM-APPROX 1999, Berkeley, United States, 8/08/99. https://doi.org/10.1007/978-3-540-48413-4_5

Approximation of multi-color discrepancy. / Doerr, Benjamin; Srivastav, Anand.
Randomization, Approximation, and Combinatorial Optimization: Algorithms and Techniques - 3rd International Workshop on Randomization and Approximation Techniques in Computer Science and 2nd International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, RANDOM-APPROX 1999, Proceedings. ed. / Jose D. P. Rolim; Alistair Sinclair; Dorit Hochbaum; Klaus Jansen. Springer Verlag, 1999. p. 39-50 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1671).

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

TY - GEN

T1 - Approximation of multi-color discrepancy

AU - Doerr, Benjamin

AU - Srivastav, Anand

N1 - Publisher Copyright: © Springer-Verlag Berlin Heidelberg 1999.

PY - 1999/1/1

Y1 - 1999/1/1

N2 - In this article we introduce (combinatorial) multi-color discrepancy and generalize some classical results from 2-color discrepancy theory to c colors. We give a recursive method that constructs c-colorings from approximations to the 2-color discrepancy. This method works for a large class of theorems like the six-standard-deviation theorem of Spencer, the Beck-Fiala theorem and the results of Matoušek, Welzl and Wernisch for bounded VC-dimension. On the other hand there are examples showing that discrepancy in c colors can not be bounded in terms of two-color discrepancy even if c is a power of 2. For the linear discrepancy version of the Beck-Fiala theorem the recursive approach also fails. Here we extend the method of oating colors to multi-colorings and prove multi-color versions of the the Beck-Fiala theorem and the Barany-Grunberg theorem.

AB - In this article we introduce (combinatorial) multi-color discrepancy and generalize some classical results from 2-color discrepancy theory to c colors. We give a recursive method that constructs c-colorings from approximations to the 2-color discrepancy. This method works for a large class of theorems like the six-standard-deviation theorem of Spencer, the Beck-Fiala theorem and the results of Matoušek, Welzl and Wernisch for bounded VC-dimension. On the other hand there are examples showing that discrepancy in c colors can not be bounded in terms of two-color discrepancy even if c is a power of 2. For the linear discrepancy version of the Beck-Fiala theorem the recursive approach also fails. Here we extend the method of oating colors to multi-colorings and prove multi-color versions of the the Beck-Fiala theorem and the Barany-Grunberg theorem.

U2 - 10.1007/978-3-540-48413-4_5

DO - 10.1007/978-3-540-48413-4_5

M3 - Conference contribution

AN - SCOPUS:22644451605

SN - 3540663290

SN - 9783540663294

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

SP - 39

EP - 50

BT - Randomization, Approximation, and Combinatorial Optimization

A2 - Rolim, Jose D. P.

A2 - Sinclair, Alistair

A2 - Hochbaum, Dorit

A2 - Jansen, Klaus

PB - Springer Verlag

T2 - 3rd International Workshop on Randomization and Approximation Techniques in Computer Science and 2nd International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, RANDOM-APPROX 1999

Y2 - 8 August 1999 through 11 August 1999

ER -

Doerr B, Srivastav A. Approximation of multi-color discrepancy. In Rolim JDP, Sinclair A, Hochbaum D, Jansen K, editors, Randomization, Approximation, and Combinatorial Optimization: Algorithms and Techniques - 3rd International Workshop on Randomization and Approximation Techniques in Computer Science and 2nd International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, RANDOM-APPROX 1999, Proceedings. Springer Verlag. 1999. p. 39-50. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-540-48413-4_5

Approximation of multi-color discrepancy

Abstract

Publication series

Conference

Access to Document

Fingerprint

Cite this