Constructive Discrepancy Minimization with Hereditary L2 Guarantees

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review

Standard

Constructive Discrepancy Minimization with Hereditary L2 Guarantees. / Larsen, Kasper Green.

36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). ed. / Rolf Niedermeier; Christophe Paul. Dagstuhl : Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH, 2019. 48 (Leibniz International Proceedings in Informatics, Vol. 126).

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review

Harvard

Larsen, KG 2019, Constructive Discrepancy Minimization with Hereditary L2 Guarantees. in R Niedermeier & C Paul (eds), 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)., 48, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH, Dagstuhl, Leibniz International Proceedings in Informatics, vol. 126, 36th International Symposium on Theoretical Aspects of Computer Science , Berlin, Germany, 13/03/2019. https://doi.org/10.4230/LIPIcs.STACS.2019.48

APA

Larsen, K. G. (2019). Constructive Discrepancy Minimization with Hereditary L2 Guarantees. In R. Niedermeier, & C. Paul (Eds.), 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019) [48] Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH. Leibniz International Proceedings in Informatics, Vol.. 126 https://doi.org/10.4230/LIPIcs.STACS.2019.48

CBE

Larsen KG. 2019. Constructive Discrepancy Minimization with Hereditary L2 Guarantees. Niedermeier R, Paul C, editors. In 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). Dagstuhl: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH. Article 48. (Leibniz International Proceedings in Informatics, Vol. 126). https://doi.org/10.4230/LIPIcs.STACS.2019.48

MLA

Larsen, Kasper Green "Constructive Discrepancy Minimization with Hereditary L2 Guarantees". and Niedermeier, Rolf Paul, Christophe (editors). 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). Dagstuhl: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH. (Leibniz International Proceedings in Informatics, Vol. 126). 2019. https://doi.org/10.4230/LIPIcs.STACS.2019.48

Vancouver

Larsen KG. Constructive Discrepancy Minimization with Hereditary L2 Guarantees. In Niedermeier R, Paul C, editors, 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). Dagstuhl: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH. 2019. 48. (Leibniz International Proceedings in Informatics, Vol. 126). https://doi.org/10.4230/LIPIcs.STACS.2019.48

Author

Larsen, Kasper Green. / Constructive Discrepancy Minimization with Hereditary L2 Guarantees. 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). editor / Rolf Niedermeier ; Christophe Paul. Dagstuhl : Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH, 2019. (Leibniz International Proceedings in Informatics, Vol. 126).

Bibtex

@inproceedings{e7bf912adc494f948adb3985a4c5d31c,
title = "Constructive Discrepancy Minimization with Hereditary L2 Guarantees",
abstract = "In discrepancy minimization problems, we are given a family of sets S =,S,A, with each Si E S a subset of some universe U =, un} of n elements. The goal is to find a coloring x : U {-1, +1} of the elements of U such that each set S E S is colored as evenly as possible. Two classic measures of discrepancy are Coo -discrepancy defined as disco, (S, x) := maxsEs E,,Es x(ui)I 2 and p2 -discrepancy defined as disc2 (S, x) := (1/ IS I,E,ses Vui)). Breakthrough work by Bansal [FOCS'10] gave a polynomial time algorithm, based on rounding an SDP, for finding a coloring x such that disc (S, x) = 0(1g n {"} herdisc,,(S)) where herdisc,,(S) is the hereditary Coo -discrepancy of S. We complement his work by giving a clean and simple 0((m n)n2) time algorithm for finding a coloring x such disc2(S, x) = 0( \/1g n {"} herdisc2(S)) where herdisc2(S) is the hereditary ?2 -discrepancy of S. Interestingly, our algorithm avoids solving an SDP and instead relies simply on computing eigendecompositions of matrices. To prove that our algorithm has the claimed guarantees, we also prove new inequalities relating both herdisc,, and herdisc2 to the eigenvalues of the incidence matrix corresponding to S. Our inequalities improve over previous work by Chazelle and Lvov [SCG'00] and by Matousek, Nikolov and Talwar [SODA'15+SCG'15]. We believe these inequalities are of independent interest as powerful tools for proving hereditary discrepancy lower bounds. Finally, we also implement our algorithm and show that it far outperforms random sampling of colorings in practice. Moreover, the algorithm finishes in a reasonable amount of time on matrices of sizes up to 10000 x 10000.",
keywords = "BOUNDS, Combinatorics, Computational Geometry, Discrepancy, Hereditary Discrepancy",
author = "Larsen, {Kasper Green}",
year = "2019",
doi = "10.4230/LIPIcs.STACS.2019.48",
language = "English",
isbn = "978-3-95977-100-9",
series = "Leibniz International Proceedings in Informatics",
publisher = "Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH",
editor = "Niedermeier, {Rolf } and Paul, {Christophe }",
booktitle = "36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)",
note = "null ; Conference date: 13-03-2019 Through 16-03-2019",

}

RIS

TY - GEN

T1 - Constructive Discrepancy Minimization with Hereditary L2 Guarantees

AU - Larsen, Kasper Green

PY - 2019

Y1 - 2019

N2 - In discrepancy minimization problems, we are given a family of sets S =,S,A, with each Si E S a subset of some universe U =, un} of n elements. The goal is to find a coloring x : U {-1, +1} of the elements of U such that each set S E S is colored as evenly as possible. Two classic measures of discrepancy are Coo -discrepancy defined as disco, (S, x) := maxsEs E,,Es x(ui)I 2 and p2 -discrepancy defined as disc2 (S, x) := (1/ IS I,E,ses Vui)). Breakthrough work by Bansal [FOCS'10] gave a polynomial time algorithm, based on rounding an SDP, for finding a coloring x such that disc (S, x) = 0(1g n " herdisc,,(S)) where herdisc,,(S) is the hereditary Coo -discrepancy of S. We complement his work by giving a clean and simple 0((m n)n2) time algorithm for finding a coloring x such disc2(S, x) = 0( \/1g n " herdisc2(S)) where herdisc2(S) is the hereditary ?2 -discrepancy of S. Interestingly, our algorithm avoids solving an SDP and instead relies simply on computing eigendecompositions of matrices. To prove that our algorithm has the claimed guarantees, we also prove new inequalities relating both herdisc,, and herdisc2 to the eigenvalues of the incidence matrix corresponding to S. Our inequalities improve over previous work by Chazelle and Lvov [SCG'00] and by Matousek, Nikolov and Talwar [SODA'15+SCG'15]. We believe these inequalities are of independent interest as powerful tools for proving hereditary discrepancy lower bounds. Finally, we also implement our algorithm and show that it far outperforms random sampling of colorings in practice. Moreover, the algorithm finishes in a reasonable amount of time on matrices of sizes up to 10000 x 10000.

AB - In discrepancy minimization problems, we are given a family of sets S =,S,A, with each Si E S a subset of some universe U =, un} of n elements. The goal is to find a coloring x : U {-1, +1} of the elements of U such that each set S E S is colored as evenly as possible. Two classic measures of discrepancy are Coo -discrepancy defined as disco, (S, x) := maxsEs E,,Es x(ui)I 2 and p2 -discrepancy defined as disc2 (S, x) := (1/ IS I,E,ses Vui)). Breakthrough work by Bansal [FOCS'10] gave a polynomial time algorithm, based on rounding an SDP, for finding a coloring x such that disc (S, x) = 0(1g n " herdisc,,(S)) where herdisc,,(S) is the hereditary Coo -discrepancy of S. We complement his work by giving a clean and simple 0((m n)n2) time algorithm for finding a coloring x such disc2(S, x) = 0( \/1g n " herdisc2(S)) where herdisc2(S) is the hereditary ?2 -discrepancy of S. Interestingly, our algorithm avoids solving an SDP and instead relies simply on computing eigendecompositions of matrices. To prove that our algorithm has the claimed guarantees, we also prove new inequalities relating both herdisc,, and herdisc2 to the eigenvalues of the incidence matrix corresponding to S. Our inequalities improve over previous work by Chazelle and Lvov [SCG'00] and by Matousek, Nikolov and Talwar [SODA'15+SCG'15]. We believe these inequalities are of independent interest as powerful tools for proving hereditary discrepancy lower bounds. Finally, we also implement our algorithm and show that it far outperforms random sampling of colorings in practice. Moreover, the algorithm finishes in a reasonable amount of time on matrices of sizes up to 10000 x 10000.

KW - BOUNDS

KW - Combinatorics

KW - Computational Geometry

KW - Discrepancy

KW - Hereditary Discrepancy

U2 - 10.4230/LIPIcs.STACS.2019.48

DO - 10.4230/LIPIcs.STACS.2019.48

M3 - Article in proceedings

SN - 978-3-95977-100-9

T3 - Leibniz International Proceedings in Informatics

BT - 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)

A2 - Niedermeier, Rolf

A2 - Paul, Christophe

PB - Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH

CY - Dagstuhl

Y2 - 13 March 2019 through 16 March 2019

ER -