Ungefähre Summe einer sortierten Liste

Kürzlich habe ich mich mit dem Problem beschäftigt, die ungefähre Summe einer Liste von sortierten nichtnegativen Zahlen zu berechnen. Für jedes feste $\epsilon>0$ wurde ein $O(\log n)$ -Zeitnäherungsschema so abgeleitet, dass es eine $(1+\epsilon)$ -Näherung für die Summe ergibt . Das Papier ist unter http://arxiv.org/abs/1112.0520 abrufbar und wurde noch nicht fertiggestellt.

Ich habe nach existierenden Arbeiten für dieses Problem gesucht, aber ich habe nur ein paar entfernt verwandte Artikel bekommen und sie zitiert. Wurde dieses Problem bereits untersucht? Wenn jemand bereits über dieses Problem recherchiert hat, lassen Sie es mich bitte wissen. Ich werde die Hilfe zu schätzen wissen und die Zitate entsprechend aktualisieren. Wenn die Ergebnisse veraltet sind, wird das Papier in eine Mülltonne geworfen.

Dieses Problem wird in dem folgenden Artikel behoben, in dem hauptsächlich allgemeinere Probleme behandelt werden: http://valis.cs.uiuc.edu/~sariel/papers/06/integrate/ .

Nachdem ich die Beweisdetails von Har-Peleds Koreset-Papier gelesen habe , verstehe ich jetzt, dass seine Methode einen O (log n) -Zeitalgorithmus für die ungefähre Summe der sortierten nichtnegativen Zahlen impliziert. Die Kernmenge wird durch eine Teilmenge von Zahlen in der sortierten Liste gebildet, und ihre Positionen hängen nur von der Listengröße n und dem Approximationsverhältnis epsilon ab. Die Gewichte aller Punkte im Coreset sind in O (log n) Zeit berechenbar. Somit liefert es einen O (log n) -Zeitalgorithmus für die ungefähre Summe einer sortierten Liste, obwohl dies in der Veröffentlichung nicht eindeutig behauptet wird. Da der Algorithmus im Beweis der Coreset-Konstruktion anstelle der behaupteten Sätze von Har-Peleds Arbeit verborgen ist, habe ich eine solche Schlussfolgerung nicht gleich nach der Überprüfung der Ergebnisse in der Arbeit gesehen.

Ich habe mein Papier überarbeitet, indem ich Abschnitt 4 gestrichen habe, der einen O (log n) -Zeitalgorithmus enthält. Das Papier von Har-Peled wird in der aktualisierten Version zitiert. Der erste Algorithmus wird immer noch beibehalten, da er eine unvergleichliche Komplexität mit der O (log n) -Zeit aufweist. Beispielsweise wird es in der O-Zeit (log log n) ausgeführt, wenn die Zahlen in der eingegebenen sortierten Liste im Bereich von 0 bis (log n) ^ {O (1)} liegen. Der Algorithmus basiert auf einer quadratischen Bereichssuche, die sich stark von der Kernsatzkonstruktion unterscheidet. Die Zeituntergrenzen werden ebenfalls beibehalten, aber leicht überarbeitet.

Jetzt habe ich eine bessere Vorstellung von den Arbeiten in dieser Zeile. Ich schätze die professionelle Hilfe der Kollegen der theoretischen Informatik auf dieser Website, die ein hervorragendes Feedback liefert, sehr. Mein überarbeitetes Papier wird in den nächsten Tagen auf derselben Archivseite verfügbar sein. Ich begrüße weitere Kommentare zu verwandten Referenzen, die möglicherweise übersehen werden.

Bin Fu

$\mathcal{O}(\log n)$$\mathcal{O}(\log n)$

$\varepsilon > 0$$0\leq a_1 \leq a_2 \leq \dots \leq a_n$

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

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

$\mathcal{O}(\log n)$$\mathcal{O}(\log n)$$\mathcal{O}(\log n)$

$\mathcal{O}(\log n)$$a_n \cdot (1+\varepsilon)^{-j}$$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.