Abstract

We present a deterministic nearly-linear time algorithm for approximating any point inside a convex polytope with a sparse convex combination of the polytope’s vertices. Our result provides a constructive proof for the Approximate Carathéodory Problem (Barman, 2015), which states that any point inside a polytope contained in the ball of radius D can be approximated to within ε in norm by a convex combination of vertices of the polytope for p 2. While for the particular case of p = 2, this can be achieved by the well-known Perceptron algorithm, we follow a more principled approach which generalizes to arbitrary p 2; furthermore, this naturally extends to domains with more complicated geometry, as it is the case for providing an approximate Birkhoffvon Neumann decomposition. Secondly, we show that the sparsity bound is tight for norms, using an argument based on anti-concentration for the binomial distribution, thus resolving an open question posed by Barman. Experimentally, we verify that our deterministic optimization-based algorithms achieve in practice much better sparsity than previously known sampling-based algorithms. We also show how to apply our techniques to SVM training and rounding fractional points in matroid and flow polytopes.