Random sampling is an efficient method to deal with constrained optimization problems in computational geometry. In a first step, one finds 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 significantly 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 \emph{sampling lemma}) which holds in an amazingly general framework, yet has not explicitly been stated in the literature. In the more restricted but still general setting of \emph{LP-type problems}, we prove tail estimates for the sampling lemma, giving Chernoff-type bounds for the number of constraints violated by the solution of a random subset. As an application, we provide the first theoretical analysis of \emph{multiple pricing}, a heuristic used in the simplex method for linear programming in order to reduce a large problem to only few small ones. This follows from our analysis of a reduction scheme for general LP-type problems, which can be considered as a simplification of algorithms by Clarkson \cite{c-lvali-95} as well as Adler and Shamir \cite{AS}. The simplified version needs less random resources and allows a Chernoff-type tail estimate.

---

Back to the publications page