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

CC BY-SA 3.0
2012-01-20T03:20:03.933Z
2012-01-20T03:25:50.570Z
2012-01-20T03:25:50.570Z
Sariel Har-Peled
<p>After reading the proof details of <a href="https://cstheory.stackexchange.com/a/9813/111">Har-Peled’s coreset paper</a>, 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.</p>

<p>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.</p>

<p>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.</p>

<p>Bin Fu </p>

CC BY-SA 3.0
2012-01-22T18:33:10.257Z
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ε
CC BY-SA 3.0
2012-01-22T19:52:18.667Z
@JɛﬀE: I think that he means the paper referred to in Sariel’s answer.
Tsuyoshi Ito
CC BY-SA 3.0
2012-01-23T13:30:03.267Z
Perhaps, but when I posted my comment, this answer was higher on the page than Sariel's.  I've added a link.
Jeffε
CC BY-SA 3.0
2012-01-24T02:35:31.497Z
My updated version is now available at http://arxiv.org/abs/1112.0520.
Bin Fu
CC BY-SA 3.0
2012-01-22T18:23:35.263Z
2012-01-23T13:31:10.473Z
2017-04-13T12:32:28.167Z
Bin Fu
<p>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. </p>

<p>Assume that $\varepsilon &gt; 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: </p>

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

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

<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2012-01-20T11:59:25.373Z
Which of Har-Peled's [ten coreset papers](http://www.dblp.org/search/index.php#query=author:sariel_har_peled:+core&qp=H1.10:W1.3:F1.4:F2.4:F3.4:F4.2) do you mean?  Also, [coreset](http://en.wikipedia.org/wiki/Coreset) ≠ [corset](http://en.wikipedia.org/wiki/Corset)!
Jeffε
CC BY-SA 3.0
2012-01-20T12:36:09.917Z
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
CC BY-SA 3.0
2012-01-20T14:51:09.347Z
Tsuyoshi: You are right. My comments should be put at the
Bin Fu
CC BY-SA 3.0
2012-01-20T14:51:28.643Z
comment area instead of the answer area. Sorry.
Bin Fu
CC BY-SA 3.0
2012-01-20T21:56:08.437Z
I dont think you understand my paper. What you wrote above is both wrong, and not what is in my paper.
Sariel Har-Peled
CC BY-SA 3.0
2012-01-20T05:38:01.427Z
2012-01-20T12:00:28.680Z
2012-01-20T12:00:28.680Z
Bin Fu
<p>Recently,  I worked on the problem for computing the approximate sum of a list of sorted nonnegative numbers. For any fixed $\epsilon&gt;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 <a href="http://arxiv.org/abs/1112.0520">http://arxiv.org/abs/1112.0520</a>, which has not been finalized.</p>

<p>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.</p>

CC BY-SA 3.0
2012-01-18T23:58:56.843Z
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
CC BY-SA 3.0
2012-01-19T06:38:31.010Z
@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
CC BY-SA 3.0
2012-01-19T09:34:32.360Z
@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
CC BY-SA 3.0
2012-01-19T16:02:20.303Z
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
CC BY-SA 3.0
2012-01-20T22:59:07.067Z
@Bin Fu: Thanks for your answer. The assumption makes sense!
Dai Le
<ds.algorithms><reference-request>
Approximate sum of a sorted list
Bin Fu
# Approximate sum of a sorted list

(Asked by: username_0 on 2012-01-18)

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.

**Tags:** ds.algorithms, reference-request

> **Comments:**
> **username_1**: 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.  
> **username_2**: @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.  
> **username_2**: @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?  
> **username_0**: 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.     username_0  
> **username_1**: @username_0: Thanks for your answer. The assumption makes sense!  

---

## 3 answers

### Answer by username_3 on 2012-01-20. Score: 7

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


---

### Answer by username_0 on 2012-01-22. Score: 1

After reading the proof details of [Har-Peled’s coreset paper](https://cstheory.stackexchange.com/a/9813/111), 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.

username_0

> **Comments:**
> **username_4**: 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.  
> **username_5**: @JɛﬀE: I think that he means the paper referred to in Sariel’s answer.  
> **username_4**: Perhaps, but when I posted my comment, this answer was higher on the page than Sariel's.  I've added a link.  
> **username_0**: My updated version is now available at http://arxiv.org/abs/1112.0520.  

---

### Answer by username_0 on 2012-01-20. Score: -3

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.

> **Comments:**
> **username_4**: Which of Har-Peled's [ten coreset papers](http://www.dblp.org/search/index.php#query=author:sariel_har_peled:+core&qp=H1.10:W1.3:F1.4:F2.4:F3.4:F4.2) do you mean?  Also, [coreset](http://en.wikipedia.org/wiki/Coreset) ≠ [corset](http://en.wikipedia.org/wiki/Corset)!  
> **username_5**: 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.  
> **username_0**: Tsuyoshi: You are right. My comments should be put at the  
> **username_0**: comment area instead of the answer area. Sorry.  
> **username_3**: I dont think you understand my paper. What you wrote above is both wrong, and not what is in my paper.  

---

