The query complexity of estimating weighted averages

DOI10.1007/s00236-011-0145-8zbMath1234.68132OpenAlexW2006202471MaRDI QIDQ766183

Amit Chakrabarti, Andrew Wirth, Anthony Wirth, Venkatesan Guruswami

Publication date: 23 March 2012

Published in: Acta Informatica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00236-011-0145-8

zbMATH Keywords

query complexityretrieval systems

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cites Work

• Lower bounds for sampling algorithms for estimating the average
• The DLT priority sampling is essentially optimal
• Priority sampling for estimation of arbitrary subset sums
• An Optimal Algorithm for Monte Carlo Estimation
• Sampling algorithms
• Estimating Sum by Weighted Sampling

This page was built for publication: The query complexity of estimating weighted averages