Constructive Discrepancy Minimization by Walking on the Edges
Authors:
- Shachar LovettSLShachar Lovett
- Raghu MekaRMRaghu Meka
- 1 January 2015
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 44 (5) , 1573-1582
Abstract
Minimizing the discrepancy of a set system is a fundamental problem in combinatorics. One of the cornerstones in this area is the celebrated six standard deviations result of Spencer [Trans. Amer. Math. Soc., 289 (1985), pp. 679--706]: In any system of $n$ sets in a universe of size $n$, there always exists a coloring which achieves discrepancy $6\sqrt{n}$. The original proof of Spencer was existential in nature and did not give an efficient algorithm to find such a coloring. Recently, a breakthrough work of Bansal [Proceedings of FOCS, 2010, pp. 3--10] gave an efficient algorithm which finds such a coloring. His algorithm was based on an SDP relaxation of the discrepancy problem and a clever rounding procedure. In this work we give a new randomized algorithm to find a coloring as in Spencer's result based on a restricted random walk we call Edge-Walk. Our algorithm and its analysis use only basic linear algebra and is truly constructive in that it does not appeal to the existential arguments, giving a ne...
Keywords
All Related Versions
This publication has 9 references indexed in Scilit:
- Approximating Bin Packing within O(log OPT · Log Log OPT) Bins2013
- Complex Graphs and Networks2006
- Geometric Discrepancy1999
- Balancing vectors and Gaussian measures ofn-dimensional convex bodiesRandom Structures & Algorithms, 1998
- AnLpVersion of the Beck–Fiala ConjectureEuropean Journal of Combinatorics, 1998
- EXTREMAL PROPERTIES OF ORTHOGONAL PARALLELEPIPEDS AND THEIR APPLICATIONS TO THE GEOMETRY OF BANACH SPACESMathematics of the USSR-Sbornik, 1989
- Six standard deviations sufficeTransactions of the American Mathematical Society, 1985
- Roth’s estimate of the discrepancy of integer sequences is nearly sharpCombinatorica, 1981
- “Integer-making” theoremsDiscrete Applied Mathematics, 1981