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

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 E_n² denote the minimum worst-case error over all possible orderings of evaluating S_n. We prove that if AT has both positive and negative numbers, it is NP-hard to compute S_n with the worst-case error equal to E_n^*. 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)E_n^*. (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]E_n^*. 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]E_n^*, while E_n^* was known to be attainable in O(nlogn) time using Huffman coding.