In this talk I will present algorithmic applications of an approximate
version of
Caratheodory's theorem. The theorem states that given a set of d-dimensional vectors
vectors X, for every vector in the convex hull of X there exists an epsilon-close
(under the
p-norm, for 2 <= p < \infinity) vector that can be expressed as a convex combination
of at
most b vectors of X, where the bound b depends on epsilon and the norm p, and is
independent of the ambient dimension d. This theorem can be obtained by instantiating
Maurey's lemma (c.f. Pisier 1980/81 and Carl 1985).

I will describe how this approximate version of Caratheodory's theorem leads novel
additive
approximation algorithms for finding (i) Nash equilibria in two-player games (ii) dense
subgraphs.