摘要：A classic result of Banaszczyk (Random Str. & Algor. 1997) states that given any
n vectors in R
m with `2-norm at most 1 and any convex body K in R
m of Gaussian measure
at least half, there exists a ±1 combination of these vectors that lies in 5K. Banaszczyk’s
proof of this result was non-constructive and it was open how to find such a ±1 combination
in polynomial time. In this paper, we give an efficient randomized algorithm to find a ±1
combination of the vectors which lies in cK for some fixed constant c > 0. This leads to new
efficient algorithms for several problems in discrepancy theory.
