On the Complexity of Approximate Sum of Sorted List

DOI10.1007/978-3-642-38756-2_29zbMATH Open1303.68070arXiv1112.0520OpenAlexW1897012829MaRDI QIDQ5405940

Publication date: 3 April 2014

Published in: Frontiers in Algorithmics and Algorithmic Aspects in Information and Management (Search for Journal in Brave)

Abstract: We consider the complexity for computing the approximate sum

a_{1} + a_{2} + . . . + a_{n}

of a sorted list of numbers

a_{1} l e a_{2} l e . . . l e a_{n}

. We show an algorithm that computes an

(1 + e p s i l o n)

-approximation for the sum of a sorted list of nonnegative numbers in an

O (1 o v e r e p s i l o n m i n (l o g n, l o g (x_{m a x} o v e r x_{m i n})) c d o t (l o g 1 o v e r e p s i l o n + l o g l o g n))

time, where

x_{m a x}

and

x_{m i n}

are the largest and the least positive elements of the input list, respectively. We prove a lower bound

O m e g a (m i n (l o g n, l o g (x_{m a x} o v e r x_{m i n}))

time for every O(1)-approximation algorithm for the sum of a sorted list of nonnegative elements. We also show that there is no sublinear time approximation algorithm for the sum of a sorted list that contains at least one negative number.

Full work available at URL: https://arxiv.org/abs/1112.0520

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)