Sublinear Time Approximate Sum via Uniform Random Sampling

2012/02/29 by Fu, Bin, Li, Wenfeng, Peng, Zhiyong
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.1202.6598

Abstract

We investigate the approximation for computing the sum a₁+...+a_n with an input of a list of nonnegative elements a₁,..., a_n. If all elements are in the range [0,1], there is a randomized algorithm that can compute an (1+ε)-approximation for the sum problem in time O(n(loglog n)\over∑_i=1ⁿ a_i), where ε 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 Ω(n\over ∑_i=1ⁿ a_i), which almost matches the upper bound, for this problem.

Related

• A Dense Hierarchy of Sublinear Time Approximation Schemes for Bin Packing
• On the Complexity of Approximate Sum of Sorted List
• Revisiting the Random Subset Sum problem
• Better Sum Estimation via Weighted Sampling
• A Fine-Grained Perspective on Approximating Subset Sum and Partition