Linear-time approximation algorithms for computing numerical summation with provably small errors

Ming Yang Kao*, Jie Wang

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

5 Scopus citations


This author was supported in part by NSF grant CCR-94241G4. Abstract. Given a multiset X = {x1,... ,xn} of real numbers, the floating-point set summation problem asks for Sn = 11 + ⋯ + Xn- Let En2 denote the minimum worst-case error over all possible orderings of evaluating Sn. We prove that if AT has both positive and negative numbers, it is NP-hard to compute Sn with the worst-case error equal to En*. We then give the first known polynomial-time approximation algorithm that has a provably small error for arbitrary X. Our algorithm incurs a worst-case error at most 2([log(n -1)] + 1)En*. (All logarithms log in this paper are base 2.) After X is sorted, it runs in O(π) time. For the case where X is either all positive or all negative, we give another approximation algorithm with a worst-case error at most [loglogn]En*. Even for unsorted X, this algorithm runs in O(n) time. Previously, the best linear-time approximation algorithm had a worst-case error at most [log n]En*, while En* was known to be attainable in O(nlogn) time using Huffman coding.

Original languageEnglish (US)
Pages (from-to)1568-1576
Number of pages9
JournalSIAM Journal on Computing
Issue number5
StatePublished - 2000


  • Addition trees
  • Approximation algorithms
  • Combinatorial optimization
  • Error analysis
  • Floating-point summation
  • Np-hardness

ASJC Scopus subject areas

  • General Computer Science
  • General Mathematics


Dive into the research topics of 'Linear-time approximation algorithms for computing numerical summation with provably small errors'. Together they form a unique fingerprint.

Cite this