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.
Organizers
Magnus M. Halldorsson
Reykjavik University
Klas Markström
Umeå University
Andrzej Rucinski
Adam Mickiewicz University
Carsten Thomassen
Technical University of Denmark, DTU

Program
Contact

Klas Markström

klas.markstrom@math.umu.se

Other
information

For practical matters at the Institute, send an e-mail to secretary@mittag-leffler.se