Please help us improve your experience by sending us a comment, question or concern

Message:

Please help transcribe this video using our simple transcription tool. You need to be logged in to do so.
Transcribe

Description

Given a set system (V,S), V=[n] and S={S_1,ldots,S_m}, the minimum discrepancy problem is to find a 2-coloring X:V -> {-1,+1}, such that each set is colored as evenly as possible, i.e. find X to minimize max_{j in [m]} |sum_{i in S_j} X(i)|.
In this paper we give the first polynomial time algorithms for discrepancy minimization, that achieve bounds similar to those known existentially using the so-called Entropy Method. We also give a first approximation-like result for discrepancy. Specifically we give efficient randomized algorithms to:
1. Construct an $O(sqrt{n})$ discrepancy coloring for general sets systems when $m=O(n)$, matching the celebrated result of Spencer up to constant factors. Previously, no algorithmic guarantee better than the random coloring bound, i.e. O((n log n)^{1/2}), was known. More generally, for $mgeq n$, we obtain a discrepancy bound of O(n^{1/2} log (2m/n)).
2. Construct a coloring with discrepancy $O(t^{1/2} log n)$, if each element lies in at most $t$ sets. This matches the (non-constructive) result of Srinivasan cite{Sr}.
3. Construct a coloring with discrepancy O(lambdalog(nm)), where lambda is the hereditary discrepancy of the set system. In particular, this implies a logarithmic approximation for hereditary discrepancy.
The main idea in our algorithms is to gradually produce a coloring by solving a sequence of semidefinite programs, while using the entropy method to guide the choice of the semidefinite program at each stage.