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 $X$, for every vector in the convex hull of $X$ there exists an epsilon-close (under the $p$-norm, for $2 \leq p < \infty$) 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.