Efficient algorithms for discrepancy minimization in convex sets

DOI10.1002/RSA.20763MaRDI QIDQ4684830zbMATH OpenOpenAlexFDO

Authors Ronen Eldan, Mohit Singh

Publication date 25 September 2018

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1409.2913

zbMATH Keywords

combinatorial discrepancy theoryrounding algorithms

Mathematics Subject Classification ID

Linear programming (90C05) Combinatorial optimization (90C27)

Abstract: 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(sqrtn)$. A geometric generalization of this result was given by Gluskin (see also Giannopoulos) who showed that every symmetric convex body $Ksubseteq{R}^n$ with Gaussian measure at least $e^{-epsilonn}$, for a small $epsilon>0$, contains a point $yinK$ where a constant fraction of coordinates of $y$ are in $-1,1$. This is often called a partial coloring result. While both these results were inherently non-algorithmic, recently Bansal (see also Lovett-Meka) gave a polynomial time algorithm for Spencer's setting and Rothvoss gave a randomized polynomial time algorithm obtaining the same guarantee as the result of Gluskin and Giannopoulos. This paper has several related results. First we prove another constructive version of the result of Gluskin and Giannopoulos via an optimization of a linear function. This implies a linear programming based algorithm for combinatorial discrepancy obtaining the same result as Spencer. Our second result gives a new approach to obtains partial colorings and shows that every convex body $Ksubseteq{R}^n$, possibly non-symmetric, with Gaussian measure at least $e^{-epsilonn}$, for a small $epsilon>0$, contains a point $yinK$ where a constant fraction of coordinates of $y$ are in $-1,1$. Finally, we give a simple proof that shows that for any $delta>0$ there exists a constant $c>0$ such that given a body $K$ with $gamm{a}_n(K)geqdelta$, a uniformly random $x$ from ${-1,1}^n$ is in $cK$ with constant probability. This gives an algorithmic version of a special case of the result of Banaszczyk.

Recommendations

• Constructive Discrepancy Minimization for Convex Sets
• On the discrepancy for boxes and polytopes
• The Gram-Schmidt walk: a cure for the Banaszczyk blues
• The Gram-Schmidt walk: a cure for the Banaszczyk blues
• On the discrepancy of convex plane sets
• A lower bound for the discrepancy of a random point set
• On the \(L_2\)-discrepancy for anchored boxes
• Expected dispersion of uniformly distributed points
• On the variance of the number of extreme points of a random convex hull
• An elementary approach to lower bounds in geometric discrepancy

Cited in

(18)

• Hierarchical design of fast minimum disagreement algorithms
• Gaussian discrepancy: a probabilistic relaxation of vector balancing
• Deterministic discrepancy minimization via the multiplicative weight update method
• Constructive Discrepancy Minimization for Convex Sets
• Discrepancy without partial colorings
• ALGORITHMS FOR L-CONVEX FUNCTION MINIMIZATION: CONNECTION BETWEEN DISCRETE CONVEX ANALYSIS AND OTHER RESEARCH FIELDS
• An algorithm for Komlós conjecture matching Banaszczyk's bound
• Constructive discrepancy minimization with hereditary L2 guarantees
• A greedy algorithm for quantizing neural networks
• The Gram-Schmidt walk: a cure for the Banaszczyk blues
• Tight hardness results for minimizing discrepancy
• The discrepancy of random rectangular matrices
• Vector balancing in Lebesgue spaces
• Discrepancy theory and related algorithms
• Searching for (sharp) thresholds in random structures: where are we now?
• Weaver's discrepancy for Gaussian random vectors
• Semidefinite optimization in discrepancy theory
• Discrepancy minimization via a self-balancing walk

This page was built for publication: Efficient algorithms for discrepancy minimization in convex sets

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