![]() |
Discrete Mathematics & Theoretical Computer Science |
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.
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
|