abstract
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