Linear-Time Approximation Algorithms for Computing Numerical Summation with Provably Small Errors

Computer Science – Data Structures and Algorithms

Scientific paper

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

Scientific paper

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.

No associations

LandOfFree

Say what you really think

Search LandOfFree.com for scientists and scientific papers. Rate them and share your experience with other people.

Rating

Linear-Time Approximation Algorithms for Computing Numerical Summation with Provably Small Errors does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Linear-Time Approximation Algorithms for Computing Numerical Summation with Provably Small Errors, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Linear-Time Approximation Algorithms for Computing Numerical Summation with Provably Small Errors will most certainly appreciate the feedback.

Rate now

     

Profile ID: LFWR-SCP-O-9570

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.