The analysis of find and versions of it

Abstract : In the running time analysis of the algorithm Find and versions of it appear as limiting distributions solutions of stochastic fixed points equation of the form X D = Sigma(i) AiXi o Bi + C on the space D of cadlag functions. The distribution of the D-valued process X is invariant by some random linear affine transformation of space and random time change. We show the existence of solutions in some generality via the Weighted Branching Process. Finite exponential moments are connected to stochastic fixed point of supremum type X D = sup(i) (A(i)X(i) + C-i) on the positive reals. Specifically we present a running time analysis of m-median and adapted versions of Find. The finite dimensional distributions converge in L-1 and are continuous in the cylinder coordinates. We present the optimal adapted version in the sense of low asymptotic average number of comparisons. The limit distribution of the optimal adapted version of Find is a point measure on the function [0, 1] there exists t -> 1 + mint, 1 - t.
Document type :
Journal articles
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2012, Vol. 14 no. 2 (2), pp.129--154
Liste complète des métadonnées

Cited literature [25 references]  Display  Hide  Download

https://hal.inria.fr/hal-00990593
Contributor : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Submitted on : Tuesday, May 13, 2014 - 4:27:45 PM
Last modification on : Thursday, September 7, 2017 - 1:03:37 AM
Document(s) archivé(s) le : Monday, April 10, 2017 - 10:50:11 PM

File

729-7418-1-PB.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00990593, version 1

Collections

Citation

Diether Knof, Uwe Roesler. The analysis of find and versions of it. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2012, Vol. 14 no. 2 (2), pp.129--154. 〈hal-00990593〉

Share

Metrics

Record views

225

Files downloads

384