CMI Seminar

Abstract:

In this talk I will present an approximate version of Caratheodory's theorem and its algorithmic applications. In particular, I will show that for every vector in the convex hull of a set of vectors X there exists a nearby (under p-norm distance, for p at least 2) vector that can be expressed as a convex combination of at most b vectors of X, where the bound b is independent of the dimension of the vectors.

Given the significance of Caratheodory's theorem, this approximate version is interesting in its own right. It also has notable algorithmic applications. Specifically, I will describe how this approximate version of Caratheodory's theorem leads to an algorithm for computing near optimal solutions of sparse bilinear and quadratic forms over the simplex. This algorithm, in particular, provides a polynomial-time approximation scheme for Nash equilibrium in games where the sum of the payoff matrices is sparse. Moreover, for arbitrary two-player games the running time of the algorithm matches the best-known upper bound, which is obtained in (Lipton, Markakis, and Mehta 2003).