Sublinear time approximate sum via uniform random sampling

DOI10.1007/978-3-642-38768-5_64MaRDI QIDQ4925287zbMATH OpenOpenAlexFDO

Authors Bin Fu, Wenfeng Li, Zhiyong Peng

Publication date 11 June 2013

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1202.6598

zbMATH Keywords

randomizationapproximate sumsublinear time

Mathematics Subject Classification ID

Randomized algorithms (68W20) Analysis of algorithms (68W40) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Abstract: We investigate the approximation for computing the sum $a_1+\mathrm{...}+a_n$ with an input of a list of nonnegative elements $a_1,\mathrm{...},a_n$. If all elements are in the range $[0,1]$, there is a randomized algorithm that can compute an $(1+epsilon)$-approximation for the sum problem in time $O(n(loglogn)oversu{m}_{i=1}^n{a}_i)$, where $epsilon$ is a constant in $(0,1)$. Our randomized algorithm is based on the uniform random sampling, which selects one element with equal probability from the input list each time. We also prove a lower bound $Omega(noversu{m}_{i=1}^n{a}_i)$, which almost matches the upper bound, for this problem.

Recommendations

• On the Complexity of Approximate Sum of Sorted List
• Estimating Sum by Weighted Sampling
• A sublinear-time approximation scheme for bin packing
• A dense hierarchy of sublinear time approximation schemes for bin packing
• A fully polynomial-time approximation scheme for approximating a sum of random variables

Cited in

(6)

• Approximate set union via approximate randomization
• Better sum estimation via weighted sampling
• Exact sublinear binomial sampling
• Estimating Sum by Weighted Sampling
• A fully polynomial-time approximation scheme for approximating a sum of random variables
• Exact Sublinear Binomial Sampling

This page was built for publication: Sublinear time approximate sum via uniform random sampling

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