Linear-time approximation algorithms for computing numerical summation with provably small errors

Ming Yang Kao*, Jie Wang

*Corresponding author for this work

Research output: Contribution to journalArticle

5 Scopus citations

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 En2 denote the minimum worst-case error over all possible orderings of evaluating Sn. We prove that if AT has both positive and negative numbers, it is NP-hard to compute Sn with the worst-case error equal to En*. 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)En*. (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]En*. 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]En*, while En* was known to be attainable in O(nlogn) time using Huffman coding.

Original languageEnglish (US)
Pages (from-to)1568-1576
Number of pages9
JournalSIAM Journal on Computing
Volume29
Issue number5
DOIs
StatePublished - Jan 1 2000

Keywords

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

ASJC Scopus subject areas

  • Computer Science(all)
  • Mathematics(all)

Fingerprint Dive into the research topics of 'Linear-time approximation algorithms for computing numerical summation with provably small errors'. Together they form a unique fingerprint.

Cite this