2026-08-07T01:51:19Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12187 2024-03-06T10:49:39Z ddc:004 open_access

A Generalization of Self-Improving Algorithms Cheng, Siu-Wing Chiu, Man-Kwun Jin, Kai Wong, Man Ting expected running time entropy sorting Delaunay triangulation 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Siu-Wing Cheng and Man-Kwun Chiu and Kai Jin and Man Ting Wong 2020 Is Part Of LIPIcs, Volume 164, 36th International Symposium on Computational Geometry (SoCG 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2020.29 urn:nbn:de:0030-drops-121873 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.29 eng https://creativecommons.org/licenses/by/3.0/legalcode