Small-size relative ( p ,ε)-approximations for well-behaved range spaces
Esther E. Ezra · 2013
We present improved upper bounds for the size of relative (p,ε)-approximation for range spaces with the following property: For any (finite) range space projected onto (that is, restricted to) a ground set of size n and for any parameter 1 ≤ k ≤ n, the number of ranges of size at most k is only nearly-linear in n and polynomial in k. Such range spaces are called "well behaved". Our bound is an improvement over the bound O(log(1/p)/ε2 p) introduced by Li et. al. [17] for the general case (where this bound has been shown to be tight in the worst case), when p l ε. We also show that such small size relative (p,ε)-approximations can be constructed in expected polynomial time.