21
$\begingroup$

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.

Improve this question
$\endgroup$
5
  • 2
    $\begingroup$ 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. $\endgroup$
    – Dai Le
    Jan 18, 2012 at 23:58
  • 5
    $\begingroup$ @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. $\endgroup$
    – Steven Stadnicki
    Jan 19, 2012 at 6:38
  • 2
    $\begingroup$ @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? $\endgroup$
    – Steven Stadnicki
    Jan 19, 2012 at 9:34
  • 4
    $\begingroup$ 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 $\endgroup$
    – Bin Fu
    Jan 19, 2012 at 16:02
  • $\begingroup$ @Bin Fu: Thanks for your answer. The assumption makes sense! $\endgroup$
    – Dai Le
    Jan 20, 2012 at 22:59

3 Answers 3

Reset to default
7
$\begingroup$

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

Improve this answer
$\endgroup$
1
$\begingroup$

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

Improve this answer
$\endgroup$
4
  • 4
    $\begingroup$ 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. $\endgroup$
    – Jeffε
    Jan 22, 2012 at 18:33
  • 1
    $\begingroup$ @JɛffE: I think that he means the paper referred to in Sariel’s answer. $\endgroup$
    – Tsuyoshi Ito
    Jan 22, 2012 at 19:52
  • $\begingroup$ Perhaps, but when I posted my comment, this answer was higher on the page than Sariel's. I've added a link. $\endgroup$
    – Jeffε
    Jan 23, 2012 at 13:30
  • $\begingroup$ My updated version is now available at arxiv.org/abs/1112.0520. $\endgroup$
    – Bin Fu
    Jan 24, 2012 at 2:35
-3
$\begingroup$

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.

Improve this answer
$\endgroup$
5
  • 1
    $\begingroup$ Which of Har-Peled's ten coreset papers do you mean? Also, coreset ≠ corset! $\endgroup$
    – Jeffε
    Jan 20, 2012 at 11:59
  • $\begingroup$ 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. $\endgroup$
    – Tsuyoshi Ito
    Jan 20, 2012 at 12:36
  • $\begingroup$ Tsuyoshi: You are right. My comments should be put at the $\endgroup$
    – Bin Fu
    Jan 20, 2012 at 14:51
  • $\begingroup$ comment area instead of the answer area. Sorry. $\endgroup$
    – Bin Fu
    Jan 20, 2012 at 14:51
  • 2
    $\begingroup$ I dont think you understand my paper. What you wrote above is both wrong, and not what is in my paper. $\endgroup$
    – Sariel Har-Peled
    Jan 20, 2012 at 21:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.