| HAL-Inria | Publications, software ... of Inria's scientists |
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.
Keywords :
optimization
randomization
Cited literature [11 references]
https://hal.inria.fr/hal-01184788
Contributor : Coordination Episciences Iam <>
Submitted on : Monday, August 17, 2015 - 4:59:47 PM
Last modification on : Thursday, June 4, 2020 - 10:34:02 AM
Long-term archiving on: : Wednesday, November 18, 2015 - 12:17:20 PM
Contributor : Coordination Episciences Iam <>
Submitted on : Monday, August 17, 2015 - 4:59:47 PM
Last modification on : Thursday, June 4, 2020 - 10:34:02 AM
Long-term archiving on: : Wednesday, November 18, 2015 - 12:17:20 PM
File
dmAH0105.pdf
Publisher files allowed on an open archive