Linear-time approximation algorithms for computing numerical summation with provably small errors
Given a multiset X = {x(1),..., x(n)} of real numbers, the floating-point set summation problem asks for S-n = x(1) +...+ x(n). Let E-n* denote the minimum worst-case error over all possible orderings of evaluating S-n. We prove that if X 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(inverted right perpendicular log(n-1) inverted left perpendicular + 1)E-n*. (All logarithms log in this paper are base 2.) After X is sorted, it runs in O(n) 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 inverted right perpendicular log log n inverted left perpendicular 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 inverted right perpendicular log n inverted left perpendicular E-n*, while E-n* was known to be attainable in O(n log n) time using Huffman coding.
approximation algorithms np-hardness floating-point summation error analysis addition trees combinatorial optimization