# Approximate sum of a sorted list

Recently, I worked on the problem for computing the approximate sum of a list of sorted nonnegative numbers. For any fixed $\epsilon>0$, an $O(\log n)$ time approximation scheme has been derived such that it gives an $(1+\epsilon)$-approximation for the sum. The paper is posted at http://arxiv.org/abs/1112.0520, which has not been finalized.

I have been looking for existing works for this problem, but I only got a few remotely related papers, and cited them. Was this problem studied before? If someone knows any existing researches about this problem, please let me know. I will appreciate the help, and update the citations accordingly. If the results are old, the paper will be dumped into a garbage can.

• Thanks for sharing the paper! Would you please give some motivation why care to study approximate sum problem for sorted lists? I mean assuming a list is sorted is a quite strong assumption. – Dai Le Jan 18 '12 at 23:58
• @DaiLe: presumably because the assumption adds quite a bit of structure to the problem; trying to find approximate sum of an unsorted list is obviously intractable because you have absolutely no information about the list other than the specific numbers you examine. – Steven Stadnicki Jan 19 '12 at 6:38
• @Bin: The lower bound on approximation of the sum in the not-all-positive case seems to come from the 'catch' that there's no good way of approximating zero; obviously this is the standard approximation scheme, but here it would seem to be better to measure error in terms of the size of the largest component rather than the size of the resultant sum; does that just make results trivial? – Steven Stadnicki Jan 19 '12 at 9:34
• In mathematics, we often see formulas for computing the sums like f(1)+f(2)+…+f(n), where f(n) is a function. Many functions are monotonic . For example, f(n)=n^k (log n). It is natural to ask whether there is an efficient way to compute this kind of sums for monotonic functions f(.). When I wrote this paper, I did have the concern if I was wasting time doing something that might be already known. This is why I came to this website to ask the help for related references since many professional people are here. Thanks for the comments. Bin Fu – Bin Fu Jan 19 '12 at 16:02
• @Bin Fu: Thanks for your answer. The assumption makes sense! – Dai Le Jan 20 '12 at 22:59

This problem is solved in the following paper, where more general problems are mostly addressed: http://valis.cs.uiuc.edu/~sariel/papers/06/integrate/ .

After reading the proof details of Har-Peled’s coreset paper, now I understand that his method implies an O(log n) time algorithm for the approximate sum of sorted nonnegative numbers. The coreset is formed by a subset of numbers in the sorted list, and their positions only depend on the list size n and approximation ratio epsilon. The weights of all points in the coreset are computable in O(log n) time. Thus, it brings an O(log n) time algorithm for approximate sum of a sorted list although it is not clearly claimed in the paper. As the algorithm is hidden in the proof of coreset construction instead of the claimed theorems of Har-Peled’s paper, I did not see such a conclusion right after checking the results in the paper.

I have revised my paper by deleting section 4 that contains an O(log n) time algorithm. Har-Peled’s paper is cited in the updated version. The first algorithm is still kept since it has a incomparable complexity with O(log n) time. For example, it runs in O(log log n) time when the numbers in the input sorted list are in the range from 0 to (log n)^{O(1)}. The algorithm is based on a quadratic region search, which is greatly different from the coreset construction. The time lower bounds are also the kept, but slightly revised.

Now I have a better idea about the works in this line. I truly appreciate the professional help from the theoretical computer science colleagues at this website, which provides an excellent feedback. My revised paper will be available in the same archive site in the next a few days. I sincerely welcome further comments about related references that might be missed.

Bin Fu

• Ahem. Which of Har-Peled's ten coreset papers do you mean? Also coreset (with two e's) is not the same as corset (with one e). One uses random sampling; the other uses whale bones. – Jeffε Jan 22 '12 at 18:33
• @JɛﬀE: I think that he means the paper referred to in Sariel’s answer. – Tsuyoshi Ito Jan 22 '12 at 19:52
• Perhaps, but when I posted my comment, this answer was higher on the page than Sariel's. I've added a link. – Jeffε Jan 23 '12 at 13:30
• My updated version is now available at arxiv.org/abs/1112.0520. – Bin Fu Jan 24 '12 at 2:35

Har-Peled’s coreset paper shows the existence of an $\mathcal{O}(\log n)$-size coreset for the approximate sum problem. This seems trivial, and does not clearly imply any $\mathcal{O}(\log n)$ time algorithm for the approximate sum problem.

Assume that $\varepsilon > 0$. is fixed. For a sorted list $0\leq a_1 \leq a_2 \leq \dots \leq a_n$, the following points form a trivial coreset for the approximate sum problem:

$\qquad a_n, \frac{a_n}{1+\varepsilon}, \frac{a_n}{(1+\varepsilon)^2}, \dots , \frac{a_n}{(1+\varepsilon)^k}$

for some $k \in \mathcal{O}\left(\frac{\log n}{\varepsilon}\right)$.

The main contribution of the approximate sum paper is an nontrivial $\mathcal{O}(\log n)$ time method to find a coreset of size $\mathcal{O}(\log n)$, which is different from the above construction. Thus, it brings an $\mathcal{O}(\log n)$ time algorithm.

With the above $\mathcal{O}(\log n)$ size coreset, one can do binary search for each point $a_n \cdot (1+\varepsilon)^{-j}$ to determine its weight, which is the number of points between $a_n \cdot (1+\varepsilon)^{-j}$ and $a_n \cdot (1+\varepsilon)^{-(j+1)}$ in the sorted list. This implies a trivial $\mathcal{O}((\log n)^2)$ time algorithm for the approximate sum problem.

• Which of Har-Peled's ten coreset papers do you mean? Also, coresetcorset! – Jeffε Jan 20 '12 at 11:59
• This should not be posted as an answer because it does not answer your question at all. It would be the best if it could be posted as a comment to Sariel’s answer, but it is too long for that. I would post it as an update to the question. – Tsuyoshi Ito Jan 20 '12 at 12:36
• Tsuyoshi: You are right. My comments should be put at the – Bin Fu Jan 20 '12 at 14:51
• comment area instead of the answer area. Sorry. – Bin Fu Jan 20 '12 at 14:51
• I dont think you understand my paper. What you wrote above is both wrong, and not what is in my paper. – Sariel Har-Peled Jan 20 '12 at 21:56