Improving the discrepancy bound for sparse matrices: better approximations for sparse lattice approximation problems
Improving the discrepancy bound for sparse matrices: better approximations for sparse lattice approximation problems
复制标题
DOI：
--
复制
发表时间：
1997-01
期刊：
影响因子：
--
通讯作者：
A. Srinivasan
中科院分区：
文献类型：
--
作者：
A. Srinivasan
Beck和Fiala提出了一种有效的逼近稀疏整数规划的方法，证明了矩阵A（E（-1，0，1），X），X的非零值不超过t，其偏差disc（A）小于2 t. Beck和Fiala的一个杰出的猜想是这里的圆盘（A）是O（d）。如果这是真的，那将是最好的可能性; o（t）的任何界都将是非常有趣的。我们在这方面取得了进展，证明了A的某些相关的差异测度是圆盘（A）上的下界，是O（t3 i4 log t）（即，o（t））。我们还证明了disc（A）= O（），从而改进了O（tlog n）的Beck-Spencer界.这些结果也适用于格逼近问题的Raghavan。我们改进的上界的差异，两个良好的研究家庭的稀疏矩阵：e排列[n]，矩形包含n个点在Rk。我们证明了前者的差异界为O（），改进了Bohus的最佳O（Llogn）。对于k = 2，3和4，这改进了后者的界限。我们还提出了一个简单的差异和沟通的复杂性之间的联系。
A powerful technique to approximate certain sparse integer programs due to Beck & Fiala, shows that matrices A E {-l,O, 1),X, 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(d). 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(t3i4 log t) (i.e., o(t)). We also show that disc(A) = O(), improving the Beck-Spencer bound of O( tlog 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: e permutations of [n], and rectangles containing n points in Rk. We show a discrepancy bound of O() for the former, improving on the previous-best O(Llogn) 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.