Estimating Sum by Weighted Sampling

DOI10.1007/978-3-540-73420-8_7MaRDI QIDQ5428797zbMATH OpenOpenAlexFDO

Authors Rina Panigrahy, Ying Xu, Rajeev Motwani

Publication date 28 November 2007

Published in Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-73420-8_7

Mathematics Subject Classification ID

Sufficient statistics and fields (62B05) Estimation in multivariate analysis (62H12) Randomized algorithms (68W20) Sampling theory in information and communication theory (94A20)

Recommendations

• Priority sampling for estimation of arbitrary subset sums
• On the Variance of Subset Sum Estimation
• Efficient stream sampling for variance-optimal estimation of subset sums
• Stream sampling for variance-optimal estimation of subset sums
• Sublinear time approximate sum via uniform random sampling

Cited in

(21)

• Improved MCMC sampling methods for estimating weighted sums in Winnow with application to DNF learning
• A sublinear-time approximation scheme for bin packing
• Sublinear-time algorithms for counting star subgraphs via edge sampling
• On approximating the stationary distribution of time-reversible Markov chains
• Optimal representative sample weighting
• The DLT priority sampling is essentially optimal
• A sample of samplers: a computational perspective on sampling
• Efficient stream sampling for variance-optimal estimation of subset sums
• scientific article; zbMATH DE number 1804098 (Why is no real title available?)
• Interval Estimation Approach to Counting by Weighing: A Sequential Scheme
• On approximating the stationary distribution of time-reversible Markov chains
• Priority sampling for estimation of arbitrary subset sums
• Stream sampling for variance-optimal estimation of subset sums
• Sublinear time approximate sum via uniform random sampling
• Lower bounds for approximating graph parameters via communication complexity
• Counting by Weighing: An Alternative Sampling Scheme
• Better sum estimation via weighted sampling
• Improved sublinear-time moment estimation using weighted sampling
• Better sum estimation via weighted sampling
• Minimizing makespan in sublinear time via weighted random sampling
• The query complexity of estimating weighted averages

This page was built for publication: Estimating Sum by Weighted Sampling

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5428797)