DMTCS Proceedings, 2007 Conference on Analysis of Algorithms, AofA 07

Font Size:  Small  Medium  Large

Randomized Optimization: a Probabilistic Analysis

Jean Cardinal, Stefan Langerman, Guy Louchard


In 1999, Chan proposed an algorithm to solve a given optimization problem: express the solution as the minimum of the solutions of several subproblems and apply the classical randomized algorithm for finding the minimum of r numbers. If the decision versions of the subproblems are easier to solve than the subproblems themselves, then a faster algorithm for the optimization problem may be obtained with randomization. In this paper we present a precise probabilistic analysis of Chan's technique.

Full Text: GZIP Compressed PostScript PostScript PDF

Valid XHTML 1.0 Transitional