DROPS

Document

DOI: 10.4230/LIPIcs.SoCG.2020.29

A Generalization of Self-Improving Algorithms

Authors: Siu-Wing Cheng, Man-Kwun Chiu, Kai Jin, and Man Ting Wong

Published in: LIPIcs, Volume 164, 36th International Symposium on Computational Geometry (SoCG 2020)

Abstract

Ailon et al. [SICOMP'11] proposed self-improving algorithms for sorting and Delaunay triangulation (DT) when the input instances x₁,⋯,x_n follow some unknown product distribution. That is, x_i comes from a fixed unknown distribution 𝒟_i, and the x_i’s are drawn independently. After spending O(n^{1+ε}) time in a learning phase, the subsequent expected running time is O((n+ H)/ε), where H ∈ {H_S,H_DT}, and H_S and H_DT are the entropies of the distributions of the sorting and DT output, respectively. In this paper, we allow dependence among the x_i’s under the group product distribution. There is a hidden partition of [1,n] into groups; the x_i’s in the k-th group are fixed unknown functions of the same hidden variable u_k; and the u_k’s are drawn from an unknown product distribution. We describe self-improving algorithms for sorting and DT under this model when the functions that map u_k to x_i’s are well-behaved. After an O(poly(n))-time training phase, we achieve O(n + H_S) and O(nα(n) + H_DT) expected running times for sorting and DT, respectively, where α(⋅) is the inverse Ackermann function.

Cite as

Siu-Wing Cheng, Man-Kwun Chiu, Kai Jin, and Man Ting Wong. A Generalization of Self-Improving Algorithms. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 29:1-29:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{cheng_et_al:LIPIcs.SoCG.2020.29,
  author =	{Cheng, Siu-Wing and Chiu, Man-Kwun and Jin, Kai and Wong, Man Ting},
  title =	{{A Generalization of Self-Improving Algorithms}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{29:1--29:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-143-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{164},
  editor =	{Cabello, Sergio and Chen, Danny Z.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.29},
  URN =		{urn:nbn:de:0030-drops-121873},
  doi =		{10.4230/LIPIcs.SoCG.2020.29},
  annote =	{Keywords: expected running time, entropy, sorting, Delaunay triangulation}
}

Document

DOI: 10.4230/LIPIcs.ISAAC.2016.39

Computing the Pattern Waiting Time: A Revisit of the Intuitive Approach

Authors: Kai Jin

Published in: LIPIcs, Volume 64, 27th International Symposium on Algorithms and Computation (ISAAC 2016)

Abstract

We revisit the waiting time of patterns in repeated independent experiments. We show that the most intuitive approach for computing the waiting time, which reduces it to computing the stopping time of a Markov chain, is optimum from the perspective of computational complexity. For the single pattern case, this approach requires us to solve a system of m linear equations, where m denotes the length of the pattern. We show that this system can be solved in O(m + n) time, where n denotes the number of possible outcomes of each single experiment. The main procedure only costs O(m) time, while a preprocessing rocedure costs O(m + n) time. For the multiple pattern case, our approach is as efficient as the one given by Li [Ann. Prob., 1980]. Our method has several advantages over other methods. First, it extends to compute the variance or even higher moment of the waiting time for the single pattern case. Second, it is more intuitive and does not entail tedious mathematics and heavy probability theory. Our main result (Theorem 2) might be of independent interest to the theory of linear equations.

Cite as

Kai Jin. Computing the Pattern Waiting Time: A Revisit of the Intuitive Approach. In 27th International Symposium on Algorithms and Computation (ISAAC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 64, pp. 39:1-39:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{jin:LIPIcs.ISAAC.2016.39,
  author =	{Jin, Kai},
  title =	{{Computing the Pattern Waiting Time: A Revisit of the Intuitive Approach}},
  booktitle =	{27th International Symposium on Algorithms and Computation (ISAAC 2016)},
  pages =	{39:1--39:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-026-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{64},
  editor =	{Hong, Seok-Hee},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2016.39},
  URN =		{urn:nbn:de:0030-drops-68096},
  doi =		{10.4230/LIPIcs.ISAAC.2016.39},
  annote =	{Keywords: Pattern Occurrence, Waiting Time, Penney’s Game, Markov Chain}
}

Search Results

Documents authored by Jin, Kai

A Generalization of Self-Improving Algorithms

Abstract

Cite as

Computing the Pattern Waiting Time: A Revisit of the Intuitive Approach

Abstract

Cite as

Thanks for your feedback!

Could not send message