Displaying similar documents to “On the number of iterations required by Von Neumann addition”

On the median-of-k version of Hoare's selection algorithm

Rudolf Grübel (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

In Hoare's (1961) original version of the algorithm   the partitioning element in the central divide-and-conquer step is chosen uniformly at random from the set in question. Here we consider a variant where this element is the median of a sample of size from . We investigate convergence in distribution of the number of comparisons required and obtain a simple explicit result for the limiting average performance of the median-of-three version.

Advice Complexity and Barely Random Algorithms

Dennis Komm, Richard Královič (2011)

RAIRO - Theoretical Informatics and Applications

Similarity:

Recently, a new measurement – the – was introduced for measuring the information content of online problems. The aim is to measure the bitwise information that online algorithms lack, causing them to perform worse than offline algorithms. Among a large number of problems, a well-known scheduling problem, , and the problem were analyzed within this model. We observe some connections between advice complexity and randomization. Our special focus goes to barely random algorithms, ...

On identifiability of mixtures of independent distribution laws

Mikhail Kovtun, Igor Akushevich, Anatoliy Yashin (2014)

ESAIM: Probability and Statistics

Similarity:

We consider representations of a joint distribution law of a family of categorical random variables (, a multivariate categorical variable) as a mixture of independent distribution laws (distribution laws according to which random variables are mutually independent). For infinite families of random variables, we describe a class of mixtures with identifiable mixing measure. This class is interesting from a practical point of view as well, as its structure clarifies principles of selecting...

Advice Complexity and Barely Random Algorithms

Dennis Komm, Richard Královič (2011)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Similarity:

Recently, a new measurement – the – was introduced for measuring the information content of online problems. The aim is to measure the bitwise information that online algorithms lack, causing them to perform worse than offline algorithms. Among a large number of problems, a well-known scheduling problem, , and the problem were analyzed within this model. We observe some connections between advice complexity and randomization. Our special focus goes to barely random algorithms, , randomized...

Convergence Rates of the POD–Greedy Method

Bernard Haasdonk (2013)

ESAIM: Mathematical Modelling and Numerical Analysis - Modélisation Mathématique et Analyse Numérique

Similarity:

Iterative approximation algorithms are successfully applied in parametric approximation tasks. In particular, reduced basis methods make use of the so-called Greedy algorithm for approximating solution sets of parametrized partial differential equations. Recently, convergence rate statements for this algorithm have been given (Buffa 2009, Binev 2010). The goal of the current study is the extension to time-dependent problems, which are typically approximated using the POD–Greedy algorithm...