Please use this identifier to cite or link to this item: http://scholarbank.nus.edu.sg/handle/10635/99537
Title: Improving the discrepancy bound for sparse matrices: Better approximations for sparse lattice approximation problems
Authors: Srinivasan, Aravind 
Issue Date: 1997
Source: Srinivasan, Aravind (1997). Improving the discrepancy bound for sparse matrices: Better approximations for sparse lattice approximation problems. Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms : 692-701. ScholarBank@NUS Repository.
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.
Source Title: Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
URI: http://scholarbank.nus.edu.sg/handle/10635/99537
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

Page view(s)

21
checked on Feb 16, 2018

Google ScholarTM

Check


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.