  Given a multiset $X=\{x_1,..., x_n\}$ of real numbers, the {\it
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(\mix)E^*_n$.\footnote{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.
