Linear-Time Approximation Algorithms for Computing Numerical Summation with Provably Small Errors
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
1999
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866909319954432000 |
|---|---|
| author | Kao, Ming-Yang Wang, Jie |
| author_facet | Kao, Ming-Yang Wang, Jie |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_cs_9907015 |
| institution | arXiv |
| publishDate | 1999 |
| record_format | arxiv |
| spellingShingle | Linear-Time Approximation Algorithms for Computing Numerical Summation with Provably Small Errors Kao, Ming-Yang Wang, Jie Data Structures and Algorithms Numerical Analysis G.1; F.2 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. |
| title | Linear-Time Approximation Algorithms for Computing Numerical Summation with Provably Small Errors |
| topic | Data Structures and Algorithms Numerical Analysis G.1; F.2 |
| url | https://arxiv.org/abs/cs/9907015 |