Abstract
We investigate the approximation for computing the sum a 1 + ⋯ + a n with an input of a list of nonnegative elements a 1, ⋯ , 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(\log\log n)\over\sum_{i=1}^n 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 \(\Omega({n\over \sum_{i=1}^n a_i})\), which almost matches the upper bound, for this problem.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Alon, N., Duffield, N., Lund, C., Thorup, M.: Estimating arbitrary subset sums with few probes. In: Proc. PODS, pp. 317–325 (2005)
Broder, A., Fontura, M., Josifovski, V., Kumar, R., Motwani, R., Nabar, S., Panigrahy, R., Tomkins, A., Xu, Y.: Estimating corpus size via queries. In: Proceedings of the 15th ACM International Conference on Information and Knowledge Management (CIKM 2006), pp. 594–603 (2006)
Canetti, R., Even, G., Goldreich, O.: Lower bounds for sampling algorithms for estimating the average. Information Processing Letters 53, 17–25 (1995)
Dagum, P., Karp, R., Luby, M., Ross, S.: An optimal algorithm for monte carlo estimation. SIAM J. Comput. 29(5), 1484–1496 (2000)
Duffield, N., Lund, C., Thorup, M.: Learn more, sample less: control of volume and variance in network measurements. IEEE Trans. on Information Theory 51, 1756–1775 (2005)
Hoefding, W.: Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association 58, 13–30 (1963)
Motwani, R., Panigrahy, R., Xu, Y.: Estimating sum by weighted sampling. In: Arge, L., Cachin, C., Jurdziński, T., Tarlecki, A. (eds.) ICALP 2007. LNCS, vol. 4596, pp. 53–64. Springer, Heidelberg (2007)
Motwani, R., Raghavan, P.: Randomized Algorithms. Cambridge University Press (2000)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Fu, B., Li, W., Peng, Z. (2013). Sublinear Time Approximate Sum via Uniform Random Sampling. In: Du, DZ., Zhang, G. (eds) Computing and Combinatorics. COCOON 2013. Lecture Notes in Computer Science, vol 7936. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-38768-5_64
Download citation
DOI: https://doi.org/10.1007/978-3-642-38768-5_64
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-38767-8
Online ISBN: 978-3-642-38768-5
eBook Packages: Computer ScienceComputer Science (R0)