Constructive Discrepancy Minimization with Hereditary L2 Guarantees

DOI10.4230/LIPICS.STACS.2019.48MaRDI QIDQ6293660arXivFDO

Authors Kasper Green Larsen

Publication date 8 November 2017

Published in arXiv

Full work available at URL https://doi.org/10.4230/LIPICS.STACS.2019.48

Mathematics Subject Classification ID

Theory of computing (68Qxx)

arXiv classification

cs.DM cs.DS math.CO

Abstract: In discrepancy minimization problems, we are given a family of sets

m a t h c a l S = S_{1}, d o t s, S_{m}

, with each

S_{i} i n m a t h c a l S

a subset of some universe

U = u_{1}, d o t s, u_{n}

of

n

elements. The goal is to find a coloring

c h i : U o - 1, + 1

of the elements of

U

such that each set

S i n m a t h c a l S

is colored as evenly as possible. Two classic measures of discrepancy are

e l l_{i} n f t y

-discrepancy defined as

e x t r m {d i s c}_{i} n f t y (m a t h c a l S, c h i) := m a x_{S i n m a t h c a l S} | s u m_{u_{i} i n S} c h i (u_{i}) |

and

e l l_{2}

-discrepancy defined as

e x t r m {d i s c}_{2} (m a t h c a l S, c h i) := s q r t (1 / | m a t h c a l S |) s u m_{S i n m a t h c a l S} l e f t (s u m_{u_{i} i n S} c h i (u_{i}) i g h t)^{2}

. Breakthrough work by Bansal gave a polynomial time algorithm, based on rounding an SDP, for finding a coloring

c h i

such that

e x t r m {d i s c}_{i} n f t y (m a t h c a l S, c h i) = O (l g n c d o t e x t r m {h e r d i s c}_{i} n f t y (m a t h c a l S))

where

e x t r m {h e r d i s c}_{i} n f t y (m a t h c a l S)

is the hereditary

e l l_{i} n f t y

-discrepancy of

m a t h c a l S

. We complement his work by giving a simple

O ((m + n) n^{2})

time algorithm for finding a coloring

c h i

such

e x t r m {d i s c}_{2} (m a t h c a l S, c h i) = O (s q r t l g n c d o t e x t r m {h e r d i s c}_{2} (m a t h c a l S))

where

e x t r m {h e r d i s c}_{2} (m a t h c a l S)

is the hereditary

e l l_{2}

-discrepancy of

m a t h c a l S

. Interestingly, our algorithm avoids solving an SDP and instead relies on computing eigendecompositions of matrices. Moreover, we use our ideas to speed up the Edge-Walk algorithm by Lovett and Meka [SICOMP'15]. To prove that our algorithm has the claimed guarantees, we show new inequalities relating

e x t r m {h e r d i s c}_{i} n f t y

and

e x t r m {h e r d i s c}_{2}

to the eigenvalues of the matrix corresponding to

m a t h c a l S

. Our inequalities improve over previous work by Chazelle and Lvov, and by Matousek et al. Finally, we also implement our algorithm and show that it far outperforms random sampling.

This page was built for publication: Constructive Discrepancy Minimization with Hereditary L2 Guarantees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6293660)