Jean Cardinal ; Stefan Langerman ; Guy Louchard - Randomized Optimization: a Probabilistic Analysis

dmtcs:3540 - Discrete Mathematics & Theoretical Computer Science, January 1, 2007, DMTCS Proceedings vol. AH, 2007 Conference on Analysis of Algorithms (AofA 07) - https://doi.org/10.46298/dmtcs.3540
Randomized Optimization: a Probabilistic Analysis

Authors: Jean Cardinal 1; Stefan Langerman 1; Guy Louchard 1

  • 1 Département d'Informatique [Bruxelles]

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.


Volume: DMTCS Proceedings vol. AH, 2007 Conference on Analysis of Algorithms (AofA 07)
Section: Proceedings
Published on: January 1, 2007
Imported on: May 10, 2017
Keywords: optimization,randomization,[INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS],[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM],[MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO],[INFO.INFO-CG] Computer Science [cs]/Computational Geometry [cs.CG]

Linked publications - datasets - softwares

Source : ScholeXplorer IsRelatedTo ARXIV 1808.06460
Source : ScholeXplorer IsRelatedTo DOI 10.3929/ethz-b-000374043
Source : ScholeXplorer IsRelatedTo DOI 10.4230/oasics.sosa.2019.9
Source : ScholeXplorer IsRelatedTo DOI 10.48550/arxiv.1808.06460
Source : ScholeXplorer IsRelatedTo HANDLE 20.500.11850/374043
  • 10.48550/arxiv.1808.06460
  • 1808.06460
  • 10.3929/ethz-b-000374043
  • 10.4230/oasics.sosa.2019.9
  • 20.500.11850/374043
Asymmetric Convex Intersection Testing

Consultation statistics

This page has been seen 144 times.
This article's PDF has been downloaded 151 times.