Approximating Dense Bipartite Subgraphs via an Approximate Version of Caratheodory's Theorem

We present algorithmic applications of an approximate version of Caratheodory's theorem. The theorem states that given a set of vectors $X$ in $\mathbb{R^d}$, for every vector in the convex hull of $X$ there exists an $\epsilon$-close (under the $p$-norm distance, for $2 \le 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 dimension $d$. This theorem can be derived by instantiating Maurey's lemma, early references to which can be found in the work of Pisier (1981) and Carl(1985). However, in this paper we present a self-contained proof of this result.

The approximate Caratheodory's theorem leads to an additive approximation algorithm for the normalized densest $k$-bipartite subgraph problem. Given a graph with n vertices and maximum degree $d$ , the developed algorithm determines a $k \times k$ bipartite  subgraph  with density  within $\epsilon$ (in  the  additive sense) of the optimal density in time $n^{O(\frac{log d}{\epsilon^2})}$.

This result appears in STOC 2015, titled `Approximating Nash Equilibria and Dense Bipartite Subgraphs via an Approximate Version of Caratheodory's Theorem' by Siddharth Barman.