Yuri Rabinovich: On multiplicative (1+ε)-approximation by a small sample, with some geometric applications

Let F be a set system over an underlying finite set X. One needs to produce a small (weighted) sample of X, such that for every set S in F, the sampled weight of S differs from its actual weight by at most a multiplicative factor of 1+ε. We ask the following meta-question: What are the structural properties of F that govern the (minimum possible) size of such a sample?

For comparison, a similar question in the context of the additive approximation has been extensively studied, and plays an important role in Learning Theory, Discrete Geometry, etc. A classical theorem of Vapnik & Chervonenkis asserts the existence of an additive ε*|X|-approximation by a sample of size bounded solely by a function of ε and the VC-dimension of F.

The analogue of the VC-dimension for the multiplicative approximation turns out to be the TRIANGULAR RANK, defined as the maximal length of a sequence of sets {S_1, S_2, ... S_t} in F such that no set in this sequence is contained in the union of the preceding ones. One of our main results is the construction of a sample as required, of size t²log(t)/ε². On the other hand, t is a lower bound on the size of any such sample for certain weightings of X.