The MathNet Korea
Information Center for Mathematical Science

논문검색

Information Center for Mathematical Science

논문검색

SIAM Journal on Computing
( Vol. 29 NO.5 / (2000))
Linear-Time Approximation Algorithms for Computing Numerical Summation with Provably Small Errors
Ming-Yang Kao, Jie Wang,
Pages. 1568-1576
Abstract 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^ast_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^ast_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(lceillog(n-1)
ceil+1)E^ast_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 $lceilloglog n
ceil
E^ast_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 $lceillog n
ceil E^ast_n$, while
$E^ast_n$ was known to be attainable in $O(n log n)$ time using
Huffman coding.
Contents 1. Introduction 2. Minimizing the wortst-case error is NP-hard 3. Approximation algorithms
Key words floating-point summation, error analysis, addition trees, combinatorial optimization, NP-hardness, approximation algorithms
Mathmatical Subject Classification