Department of Computer Science | Institute of Theoretical Computer Science

Clarksons algorithm is a two-staged randomized algorithm for solving
linear programs. This algorithm has been simplified and adapted to fit
the framework of LP-type problems. In this framework we can tackle a
number of non-linear problems such as computing the smallest enclosing
ball of a set of points in R^d . In 2006, it has been shown that the
algorithm in its original form works for violator spaces too, which
are a proper general- ization of LP-type problems. It was not clear,
however, whether previous simplifications of the algorithm carry over
to the new setting. In this paper we show the following theoretical
results: (a) It is shown, for the first time, that Clarksons second
stage can be simplified. (b) The previous simplifications of Clarksons
first stage carry over to the violator space setting. (c) Furthermore,
we show the equivalence of violator spaces and partitions of the
hypercube by hypercubes.