Practical aspects of ℓ₀-sampling algorithms - Lopes, Juan P. A.; Oliveira, Fabiano S.; Barbosa, Valmir C. (Anais do Encontro de Teoria da Computação (ETC); 2018: Anais do III Encontro de Teoria da Computação, 2018)
The ℓ₀-sampling problem plays an important role in streaming graph algorithms. In this paper, we revisit a near-optimal ℓ₀-sampling algorithm, proposing a variant that allows proving a tighter upper bound for the probability of failure. We compare experimental results of both variants, providing empirical evidence of their applicability in real-case scenarios.