Journal
ALGORITHMICA
Volume 29, Issue 3, Pages 371-395Publisher
SPRINGER-VERLAG
DOI: 10.1007/s004530010046
Keywords
discrepancy; lattice approximation; parallel algorithms; derandomization; geometric sampling
Ask authors/readers for more resources
We show that several discrepancy-like problems can be solved in NC nearly achieving the discrepancies guaranteed by a probabilistic analysis and achievable sequentially. For example, we describe an NC algorithm that given a set system (X, S), where X is a ground set and S subset of or equal to 2(X), computes a set R subset of or equal to X so that for each S is an element of S the discrepancy parallel toR boolean AND S\ - \(R) over bar boolean AND S parallel to is O(root \S\log\S\). Whereas previous NC algorithms could only achieve discrepancies O(root \S\(1+epsilon) log\S\) with epsilon > 0, ours matches the probabilistic bound within a multiplicative factor 1 + o(1). Other problems whose NC solution we improve are lattice approximation, E-approximations of range spaces with constant VC-exponent, sampling in geometric configuration spaces, approximation of integer linear programs, and edge coloring of graphs.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available