Research output: Contribution to book/anthology/report/proceeding › Article in proceedings › Research › peer-review

- https://doi.org/10.4230/LIPIcs.STACS.2019.48
Final published version

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.

Original language | English |
---|---|

Title of host publication | 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019) |

Editors | Rolf Niedermeier, Christophe Paul |

Number of pages | 13 |

Place of publication | Dagstuhl |

Publisher | Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH |

Publication year | 2019 |

Article number | 48 |

ISBN (print) | 978-3-95977-100-9 |

DOIs | |

Publication status | Published - 2019 |

Event | 36th International Symposium on Theoretical Aspects of Computer Science - Berlin, Germany Duration: 13 Mar 2019 → 16 Mar 2019 |

Conference | 36th International Symposium on Theoretical Aspects of Computer Science |
---|---|

Land | Germany |

By | Berlin |

Periode | 13/03/2019 → 16/03/2019 |

Series | Leibniz International Proceedings in Informatics |
---|---|

Volume | 126 |

ISSN | 1868-8969 |

- BOUNDS, Combinatorics, Computational Geometry, Discrepancy, Hereditary Discrepancy

See relations at Aarhus University Citationformats

ID: 170314477