## Abstract

This author was supported in part by NSF grant CCR-94241G4. Abstract. Given a multiset X = {x1,... ,xn} of real numbers, the floating-point set summation problem asks for Sn = 11 + ⋯ + Xn- Let E_{n}^{2} denote the minimum worst-case error over all possible orderings of evaluating S_{n}. We prove that if AT 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([log(n -1)] + 1)E_{n}^{*}. (All logarithms log in this paper are base 2.) After X is sorted, it runs in O(π) 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 [loglogn]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 [log n]E_{n}^{*}, while E_{n}^{*} was known to be attainable in O(nlogn) time using Huffman coding.

Original language | English (US) |
---|---|

Pages (from-to) | 1568-1576 |

Number of pages | 9 |

Journal | SIAM Journal on Computing |

Volume | 29 |

Issue number | 5 |

DOIs | |

State | Published - 2000 |

## Keywords

- Addition trees
- Approximation algorithms
- Combinatorial optimization
- Error analysis
- Floating-point summation
- Np-hardness

## ASJC Scopus subject areas

- General Computer Science
- General Mathematics