Larsen, Kasper Green
Constructive Discrepancy Minimization with Hereditary L2 Guarantees
Abstract
In discrepancy minimization problems, we are given a family of sets S = {S_1,...,S_m}, with each S_i in S a subset of some universe U = {u_1,...,u_n} of n elements. The goal is to find a coloring chi : U > {1,+1} of the elements of U such that each set S in S is colored as evenly as possible. Two classic measures of discrepancy are l_inftydiscrepancy defined as disc_infty(S,chi):=max_{S in S}  sum_{u_i in S} chi(u_i)  and l_2discrepancy defined as disc_2(S,chi):=sqrt{(1/S) sum_{S in S} (sum_{u_i in S} chi(u_i))^2}. Breakthrough work by Bansal [FOCS'10] gave a polynomial time algorithm, based on rounding an SDP, for finding a coloring chi such that disc_infty(S,chi) = O(lg n * herdisc_infty(S)) where herdisc_infty(S) is the hereditary l_inftydiscrepancy of S. We complement his work by giving a clean and simple O((m+n)n^2) time algorithm for finding a coloring chi such disc_2(S,chi) = O(sqrt{lg n} * herdisc_2(S)) where herdisc_2(S) is the hereditary l_2discrepancy 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_infty and herdisc_2 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.
BibTeX  Entry
@InProceedings{larsen:LIPIcs:2019:10287,
author = {Kasper Green Larsen},
title = {{Constructive Discrepancy Minimization with Hereditary L2 Guarantees}},
booktitle = {36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)},
pages = {48:148:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771009},
ISSN = {18688969},
year = {2019},
volume = {126},
editor = {Rolf Niedermeier and Christophe Paul},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/10287},
doi = {10.4230/LIPIcs.STACS.2019.48},
annote = {Keywords: Discrepancy, Hereditary Discrepancy, Combinatorics, Computational Geometry}
}
2019
Keywords: 

Discrepancy, Hereditary Discrepancy, Combinatorics, Computational Geometry 
Seminar: 

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

Issue date: 

2019 
Date of publication: 

2019 