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

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. 1. Introduction 2. Minimizing the wortst-case error is NP-hard 3. Approximation algorithms floating-point summation, error analysis, addition trees, combinatorial optimization, NP-hardness, approximation algorithms