Department of Computer Science | Institute of Theoretical Computer Science

Following recent work of Clarkson, we translate the coreset framework
to the problems of finding the point closest to the origin inside a
polytope, finnding the shortest distance between two polytopes,
Perceptrons, and soft- as well as hard-margin Support Vector Machines
(SVM). We prove asymptotically matching upper and lower bounds on the
size of coresets, stating that -coresets of size d(1 + o(1))E^* do
always exist as ! 0, and that this is best possible. The crucial
quantity E^* is what we call the excentricity of a polytope, or a pair
of polytopes. Additionally, we prove linear convergence speed of
Gilbert's algorithm, one of the earliest known approximation algo-
rithms for polytope distance, and generalize both the algo- rithm and
the proof to the two polytope case. Interestingly, our coreset bounds
also imply that we can for the rst time prove matching upper and lower
bounds for the sparsity of Perceptron and SVM solutions.