Linear-Time Approximation Algorithms for Computing Numerical Summation with Provably Small Errors
Ming‐Yang Kao, Jie Wang · SIAM Journal on Computing · 2000
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(\lceil\log(n-1)\rceil+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 $\lceil\log\log n\rceil 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 $\lceil\log n\rceil E^*_n$, while $E^*_n$ was known to be attainable in O(n log n) time using Huffman coding.