Analysis of algorithms and randomized algorithms

In papers by Rösler (1991, 1992) and Rachev and Rüschendorf (1990, 1995) a new method was developed for the analysis of algorithms used in computer science and stochastics. It is a contraction method based on the use of suitable minimal metrics. Using this method it was possible to describe the asymptotic behaviour for a great class of recursive algorithms and general recursive structures. The example classes being approachable by this method include in particular different search and sort methods as well as algorithms for the resolution of collisions in networks (CRI), algorithms in the context of GARCH models, tree algorithms, but also bootstrap methods and iterative function systems used for image encoding. Further topics are the construction of multifractal measures, products of random matrices as well as the fractal encoding of images and the exploration of GARCH models for financial data. Besides the analysis of algorithms also randomised algorithms of the Monte Carlo type for combinatorical and graphtheoretical problems are developed and analysed for example for spanning trees or for grid problems.

Phone: 0761/203-5665
Email: ruschen@stochastik.uni-freiburg.de

Start of project: 2002
End of project: (unlimited)

Albert-Ludwigs-University Freiburg
Prof. Dr. Ludger Rüschendorf
Abteilung für Mathematische Stochastik
Prof. Dr. Ludger Rüschendorf
Ernst-Zermelo-Straße 1
79104 Freiburg
Germany

Phone: 0761/203-5664
Fax: 0761/203-5661
Email: sekretariat@stochastik.uni-freiburg.de
http://www.stochastik.uni-freiburg.de/rueschendorf
Actual Research Report

Analyse von Algorithmen, Konstruktion multifraktaler Maße, P

• Fehrenbach J, Rüschendorf L: A multicommodity flow for the counting of spanning trees. Preprint Uni Freiburg, 2003; 25.
• Neininger R, Rüschendorf L: Analysis of algorithms by the contraction method: additive and max-recursive sequences. Preprint Uni Freiburg, 2003; 24.
• Neininger R, Rüschendorf L: Multivariate aspects of the contraction method. Preprint Uni Freiburg, 2003; 19.
• Neininger R, Rüschendorf L: Rates of convergence for Quicksort. Journal of Algorithms, 2002; 44 (1): 52-62.
• Neininger R, Rüschendorf L: On the contraction method with degenerate limit equation. Preprint Uni Freiburg, 2002; 19.
• Anthes B, Rüschendorf L: On the weighted Euclidean matching problem in R^d-dimensions. Applicationes Mathematicae, 2001; 28: 181-190.
• Cramer M, Rüschendorf L: Convergence of two-dimensional branching recursions. Journal Computational Appl. Math., 2001; 130: 53-73.
• Neininger R, Rüschendorf L: Limit laws for partial match queries in quadtrees. The Annals of Applied Probability, 2001; 11 (2): 452-469.
• Hutchinson J.R, Rüschendorf L: Random fractals and probability metrics. Advances of Appl. Prob., 2000; 32: 925-947.
• Hutchinson J.R, Rüschendorf L: Random fractal measures via the contraction method. Indiana Univ. Math. J., 1998; 47: 471-488.
• Cramer M: Stochastic analysis of the Merge-Sort algorithm. J. Random Struct. Algorithms, 1997; 1/11: 81-96.
• Feldman P, Rachev S.T, Rüschendorf L: Limiting distribution of the collision resolution interval. Statistica Neerlandica, 1997; 51: 1-22.
• Cramer M: A note concerning the limit distribution of the quicksort algorithm. RAIRO, Inform. Theor. Appl., 1996; 30: 195-207.
• Cramer M, Rüschendorf L: Analysis of recursive algorithms by the contraction method. In: Heyde, C.C. et al. (Hrsg.): Athens Conference on Applied Probability and Time Series Analysis. Athens, Greece, March 22-26, 1995. In Honor of J.M. Gani. Lecture Notes of Statistics, 114, Springer, 1996; 18-33.
• Cramer M, Rüschendorf L: Convergence of a branching type recursion. Ann. Inst. Henri Poincaré, 1996; 32: 725-741.
• Cramer M: Stochastische Analyse rekursiver Algorithmen mit idealen Metriken. Dissertation Universität Freiburg, 1995: p.283.
• Feldman P, Rachev S.T, Rüschendorf L.: Limit theorems for recursive algorithms. J. Comp. Appl. Mathematics, 1995; 56: 169-182.
• Rachev S.T, Rüschendorf L: Probability metrics and recursive algorithms. Adv. Appl. Prob., 1995; 27: 770-779.
• Rüschendorf L: Convergence of the iterative proportional fitting procedure. Ann. Statistics, 1995; 23: 1160-1174.