Title: Algorithmic Applications of An Approximate Version of Caratheodory's Theorem
Speaker: Siddharth Barman (IISc CSA)
Date: 21 October 2016
Time: 2:15 – 3:15 pm
Venue: LH-1, Mathematics Department
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.