A Simple Sampling Lemma: Analysis and Applications in Geometric Optimization¤

Random sampling is an e±cient method to deal with constrained optimization problems in computational geometry. In a ¯rst step, one ¯nds the optimal solution subject to a random subset of the constraints; in many cases, the expected number of constraints still violated by that solution is then signi¯cantly smaller than the overall number of constraints that remain. This phenomenon can be exploited in several ways, and typically results in simple and asymptotically fast algorithms. Very often the analysis of random sampling in this context boils down to a simple identity (the sampling lemma) which holds in a general framework, yet has not been stated explicitly in the literature. In the more restricted but still general setting of LP-type problems, we prove tail esti-mates for the sampling lemma, giving Cherno®-type bounds for the number of constraints violated by the solution of a random subset. As an application, we provide the ¯rst the-oretical analysis of multiple pricing, a heuristic used in the simplex method for linear pro-gramming in order to reduce a large problem to few small ones. This follows from our analysis of a reduction scheme for general LP-type problems, which can be considered as a simpli¯cation of an algorithm due to Clarkson. The simpli¯ed version needs less random resources and allows a Cherno®-type tail estimate.