Skip to Main content Skip to Navigation
Conference papers

Randomized Optimization: a Probabilistic Analysis

Abstract : 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.
Complete list of metadata

Cited literature [11 references]  Display  Hide  Download
Contributor : Coordination Episciences Iam Connect in order to contact the contributor
Submitted on : Monday, August 17, 2015 - 4:59:47 PM
Last modification on : Tuesday, October 19, 2021 - 12:55:37 PM
Long-term archiving on: : Wednesday, November 18, 2015 - 12:17:20 PM


Publisher files allowed on an open archive




Jean Cardinal, Stefan Langerman, Guy Louchard. Randomized Optimization: a Probabilistic Analysis. 2007 Conference on Analysis of Algorithms, AofA 07, 2007, Juan les Pins, France. pp.57-78, ⟨10.46298/dmtcs.3540⟩. ⟨hal-01184788⟩



Record views


Files downloads