Search Results

Documents authored by Neininger, Ralph

Document
DOI: 10.4230/LIPIcs.AofA.2024.9
On Fluctuations of Complexity Measures for the FIND Algorithm

Authors: Jasper Ischebeck and Ralph Neininger

Published in: LIPIcs, Volume 302, 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024)

Abstract
The FIND algorithm (also called Quickselect) is a fundamental algorithm to select ranks or quantiles within a set of data. It was shown by Grübel and Rösler that the number of key comparisons required by FIND as a process of the quantiles α ∈ [0,1] in a natural probabilistic model converges after normalization in distribution within the càdlàg space D[0,1] endowed with the Skorokhod metric. We show that the process of the residuals in the latter convergence after normalization converges in distribution to a mixture of Gaussian processes in D[0,1] and identify the limit’s conditional covariance functions. A similar result holds for the related algorithm QuickVal. Our method extends to other cost measures such as the number of swaps (key exchanges) required by FIND or cost measures which are based on key comparisons but take into account that the cost of a comparison between two keys may depend on their values, an example being the number of bit comparisons needed to compare keys given by their bit expansions.
Cite as

Jasper Ischebeck and Ralph Neininger. On Fluctuations of Complexity Measures for the FIND Algorithm. In 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 302, pp. 9:1-9:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{ischebeck_et_al:LIPIcs.AofA.2024.9,
  author =	{Ischebeck, Jasper and Neininger, Ralph},
  title =	{{On Fluctuations of Complexity Measures for the FIND Algorithm}},
  booktitle =	{35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024)},
  pages =	{9:1--9:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-329-4},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{302},
  editor =	{Mailler, C\'{e}cile and Wild, Sebastian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2024.9},
  URN =		{urn:nbn:de:0030-drops-204440},
  doi =		{10.4230/LIPIcs.AofA.2024.9},
  annote =	{Keywords: FIND, Quickselect, rank selection, probabilistic analysis of algorithms, weak convergence, functional limit theorem}
}
Document
DOI: 10.4230/LIPIcs.AofA.2024.25
Patricia’s Bad Distributions

Authors: Louigi Addario-Berry, Pat Morin, and Ralph Neininger

Published in: LIPIcs, Volume 302, 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024)

Abstract
The height of a random PATRICIA tree built from independent, identically distributed infinite binary strings with arbitrary diffuse probability distribution μ on {0,1}^ℕ is studied. We show that the expected height grows asymptotically sublinearly in the number of leaves for any such μ, but can be made to exceed any specific sublinear growth rate by choosing μ appropriately.
Cite as

Louigi Addario-Berry, Pat Morin, and Ralph Neininger. Patricia’s Bad Distributions. In 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 302, pp. 25:1-25:8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{addarioberry_et_al:LIPIcs.AofA.2024.25,
  author =	{Addario-Berry, Louigi and Morin, Pat and Neininger, Ralph},
  title =	{{Patricia’s Bad Distributions}},
  booktitle =	{35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024)},
  pages =	{25:1--25:8},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-329-4},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{302},
  editor =	{Mailler, C\'{e}cile and Wild, Sebastian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2024.25},
  URN =		{urn:nbn:de:0030-drops-204600},
  doi =		{10.4230/LIPIcs.AofA.2024.25},
  annote =	{Keywords: PATRICIA tree, random tree, height of tree, analysis of algorithms}
}
Document
DOI: 10.4230/LIPIcs.AofA.2022.14
On the Contraction Method with Reduced Independence Assumptions

Authors: Ralph Neininger and Jasmin Straub

Published in: LIPIcs, Volume 225, 33rd International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2022)

Abstract
Recursive sequences of laws of random variables (and random vectors) are considered where an independence assumption which is usually made within the setting of the contraction method is dropped. This restricts the study to sequences which after normalization lead to asymptotic normality. We provide a general univariate central limit theorem which can directly be applied to problems from the analysis of algorithms and random recursive structures without further knowledge of the contraction method. Also multivariate central limit theorems are shown and bounds on rates of convergence are provided. Examples include some previously shown central limit analogues as well as new applications on Fibonacci matchings.
Cite as

Ralph Neininger and Jasmin Straub. On the Contraction Method with Reduced Independence Assumptions. In 33rd International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 225, pp. 14:1-14:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{neininger_et_al:LIPIcs.AofA.2022.14,
  author =	{Neininger, Ralph and Straub, Jasmin},
  title =	{{On the Contraction Method with Reduced Independence Assumptions}},
  booktitle =	{33rd International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2022)},
  pages =	{14:1--14:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-230-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{225},
  editor =	{Ward, Mark Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2022.14},
  URN =		{urn:nbn:de:0030-drops-161008},
  doi =		{10.4230/LIPIcs.AofA.2022.14},
  annote =	{Keywords: Probabilistic Analysis of Algorithms, random Trees, weak Convergence, Probability Metrics, Contraction Method}
}
Document
DOI: 10.4230/LIPIcs.AofA.2020.22
Convergence Rates in the Probabilistic Analysis of Algorithms

Authors: Ralph Neininger and Jasmin Straub

Published in: LIPIcs, Volume 159, 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)

Abstract
In this extended abstract a general framework is developed to bound rates of convergence for sequences of random variables as they mainly arise in the analysis of random trees and divide-and-conquer algorithms. The rates of convergence are bounded in the Zolotarev distances. Concrete examples from the analysis of algorithms and data structures are discussed as well as a few examples from other areas. They lead to convergence rates of polynomial and logarithmic order. Our results show how to obtain a significantly better bound for the rate of convergence when the limiting distribution is Gaussian.
Cite as

Ralph Neininger and Jasmin Straub. Convergence Rates in the Probabilistic Analysis of Algorithms. In 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 159, pp. 22:1-22:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{neininger_et_al:LIPIcs.AofA.2020.22,
  author =	{Neininger, Ralph and Straub, Jasmin},
  title =	{{Convergence Rates in the Probabilistic Analysis of Algorithms}},
  booktitle =	{31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)},
  pages =	{22:1--22:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-147-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{159},
  editor =	{Drmota, Michael and Heuberger, Clemens},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2020.22},
  URN =		{urn:nbn:de:0030-drops-120529},
  doi =		{10.4230/LIPIcs.AofA.2020.22},
  annote =	{Keywords: weak convergence, probabilistic analysis of algorithms, random trees, probability metrics}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact