Sampling algorithms

DOI10.1145/380752.380810zbMath1323.68292OpenAlexW1988624553MaRDI QIDQ5175979

Ziv Bar-Yossef, D. Sivakumar, Ravi Kumar

Publication date: 27 February 2015

Published in: Proceedings of the thirty-third annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/380752.380810

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Statistical sampling theory and related topics (62D99) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (14)

Sublinear algorithms for approximating string compressibility ⋮ Optimal sampling from sliding windows ⋮ An Automatic Inequality Prover and Instance Optimal Identity Testing ⋮ Streaming techniques and data aggregation in networks of tiny artefacts ⋮ Range partitioning within sublinear time: algorithms and lower bounds ⋮ Sample complexity of the distinct elements problem ⋮ Predicting winner and estimating margin of victory in elections using sampling ⋮ Non-interactive proofs of proximity ⋮ Sublinear Algorithms in the External Memory Model ⋮ Adversary lower bounds for nonadaptive quantum algorithms ⋮ Three theorems regarding testing graph properties ⋮ Range partitioning within sublinear time in the external memory model ⋮ A Sample of Samplers: A Computational Perspective on Sampling ⋮ The query complexity of estimating weighted averages

Cites Work

• A constant-factor approximation algorithm for the k -median problem (extended abstract)

This page was built for publication: Sampling algorithms