Premium
Efficient algorithms for discrepancy minimization in convex sets
Author(s) -
Eldan Ronen,
Singh Mohit
Publication year - 2018
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20763
Subject(s) - mathematics , combinatorics , constant (computer programming) , generalization , regular polygon , time complexity , simple (philosophy) , gaussian measure , measure (data warehouse) , convex body , discrete mathematics , convex optimization , gaussian , algorithm , computer science , mathematical analysis , philosophy , physics , geometry , epistemology , quantum mechanics , database , programming language
A result of Spencer states that every collection of n sets over a universe of size n has a coloring of the ground set with { − 1 , + 1 } of discrepancy O ( n ) . A geometric generalization of this result was given by Gluskin (see also Giannopoulos) who showed that every symmetric convex body K ⊆ R nwith Gaussian measure at leaste − ϵ n, for a small ϵ > 0 , contains a point y ∈ K where a constant fraction of coordinates of y are in { − 1 , 1 } . This is often called a partial coloring result. While the proofs of both these results were inherently non‐algorithmic, recently Bansal (see also Lovett‐Meka) gave a polynomial time algorithm for Spencer's setting and Rothvoß gave a randomized polynomial time algorithm obtaining the same guarantee as the result of Gluskin and Giannopoulos. This paper contains several related results which combine techniques from convex geometry to analyze simple and efficient algorithms for discrepancy minimization. First, we prove another constructive version of the result of Gluskin and Giannopoulos, in which the coloring is attained via the optimization of a linear function. This implies a linear programming based algorithm for combinatorial discrepancy obtaining the same result as Spencer. Our second result suggests a new approach to obtain partial colorings, which is also valid for the non‐symmetric case. It shows that every (possibly non‐symmetric) convex body K ⊆ R n , with Gaussian measure at leaste − ϵ n, for a small ϵ > 0 , contains a point y ∈ K where a constant fraction of coordinates of y are in { − 1 , 1 } . Finally, we give a simple proof that shows that for any δ > 0 there exists a constant c > 0 such that given a body K withγ n ( K ) ≥ δ , a uniformly random x from{ − 1 , 1 } nis in cK with constant probability. This gives an algorithmic version of a special case of the result of Banaszczyk.