Approximating Nash Equilibria and Dense Subgraphs via an Approximate Version of Carathéodory's Theorem

Siddharth Barman

We present algorithmic applications of an approximate version of Carathéodory's theorem. The theorem states that given a set of vectors $X$ in ${\mathbb{R}}^d$, for every vector in t…