Seminar

# ON MULTIPLICATIVE (1+\epsilon)-APPROXIMATION BY A SMALL SAMPLE, WITH SOME GEOMETRIC APPLICATIONS

#### Graphs, Hypergraphs, and Computing

#### 28 January 14:00 - 15:00

#### Yuri Rabinovich - University of Haifa

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+\epsilon. 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 epsilon*|X| - approximation by a sample of size bounded solely by a function of \epsilon 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^2 log(t) / \epsilon^2. On the other hand, t is a lower bound on the size of any such sample for certain weightings of X.

Time permitting, we shall present some applications to L_1 metrics and to Euclidean volumes.

Based on a joint work with Ilan Newman.

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 epsilon*|X| - approximation by a sample of size bounded solely by a function of \epsilon 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^2 log(t) / \epsilon^2. On the other hand, t is a lower bound on the size of any such sample for certain weightings of X.

Time permitting, we shall present some applications to L_1 metrics and to Euclidean volumes.

Based on a joint work with Ilan Newman.

Organizers

Magnus M. Halldorsson

Reykjavik University

Klas Markström

Umeå University

Andrzej Rucinski

Adam Mickiewicz University

Carsten Thomassen

Technical University of Denmark, DTU