Improving the discrepancy bound for sparse matrices: Better approximations for sparse lattice approximation problems

Abstract

A powerful technique to approximate certain sparse integer programs due to Beck & Fiala, shows that matrices A∈{-1, 0, 1}m×n with no column having more than t nonzeroes, have discrepancy disc(A) less than 2t. An outstanding conjecture of Beck & Fiala is that this disc(A) here is O(√t). This, if true, would be best-possible; any bound of o(t) would be very interesting. We make progress on this by showing that certain related discrepancy measures of A that are lower bounds on disc(A), are O(t3/4log t) (i.e., o(t)). We also show that disc(A) = O(√t log n), improving the Beck-Spencer bound of O(√t log t log n). These results also apply to the lattice approximation problem of Raghavan. We show improved upper bounds on the discrepancy of two well-studied families of sparse matrices: l permutations of [n], and rectangles containing n points in Rk. We show a discrepancy bound of O(√l log n) for the former, improving on the previous-best O(l log n) due to Bohus. This improves the bounds for the latter, for k = 2, 3 and 4. We also present a simple connection between discrepancy and communication complexity.