Przybliżona suma posortowanej listy

Ostatnio pracowałem nad problemem obliczania przybliżonej sumy listy posortowanych liczb nieujemnych. Dla każdego ustalonego opracowano schemat aproksymacji czasu , który daje przybliżenie dla sumy. Artykuł opublikowano na stronie http://arxiv.org/abs/1112.0520 , który nie został jeszcze sfinalizowany.O ( log n ) ( 1 + ϵ $\epsilon>0$$O(\log n)$$(1+\epsilon)$

Szukałem istniejących prac dotyczących tego problemu, ale dostałem tylko kilka zdalnie powiązanych artykułów i zacytowałem je. Czy ten problem był wcześniej badany? Jeśli ktoś zna jakiekolwiek istniejące badania dotyczące tego problemu, daj mi znać. Będę wdzięczny za pomoc i odpowiednio zaktualizuję cytowania. Jeśli wyniki są stare, papier zostanie zrzucony do kosza na śmieci.

Ten problem został rozwiązany w następującym artykule, w którym poruszono głównie bardziej ogólne problemy: http://valis.cs.uiuc.edu/~sariel/papers/06/integrate/ .

Po zapoznaniu się ze szczegółowymi dowodami artykułu z zestawu rdzeni Har-Peleda , teraz rozumiem, że jego metoda implikuje algorytm czasowy O (log n) dla przybliżonej sumy posortowanych liczb nieujemnych. Zestaw podstawowy składa się z podzbioru liczb na posortowanej liście, a ich pozycje zależą tylko od wielkości listy n i współczynnika przybliżenia epsilon. Wagi wszystkich punktów w zestawie rdzeni są obliczalne w czasie O (log n). W ten sposób wprowadza algorytm czasowy O (log n) dla przybliżonej sumy posortowanej listy, chociaż nie jest to wyraźnie określone w dokumencie. Ponieważ algorytm jest ukryty w dowodzie budowy zestawu rdzeniowego zamiast twierdzonych twierdzeń w pracy Har-Peleda, nie widziałem takiego wniosku zaraz po sprawdzeniu wyników w pracy.

Poprawiłem swój artykuł, usuwając sekcję 4, która zawiera algorytm czasowy O (log n). Artykuł Har-Peleda jest cytowany w zaktualizowanej wersji. Pierwszy algorytm jest nadal przechowywany, ponieważ ma nieporównywalną złożoność z czasem O (log n). Na przykład działa w czasie O (log log n), gdy liczby na liście posortowanej są w zakresie od 0 do (log n) ^ {O (1)}. Algorytm oparty jest na kwadratowym wyszukiwaniu regionu, co znacznie różni się od budowy zestawu rdzeniowego. Dolne granice czasu są również zachowane, ale nieco zmienione.

Teraz mam lepszy pomysł na prace w tej linii. Naprawdę doceniam profesjonalną pomoc kolegów teoretycznych z dziedziny informatyki na tej stronie, która stanowi doskonałą informację zwrotną. Mój poprawiony artykuł będzie dostępny w tym samym archiwum za kilka dni. Z poważaniem przyjmuję dalsze komentarze dotyczące odnośników, które mogą zostać pominięte.

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)$

Głównym wkładem przybliżonej sumy papieru jest nietrywialne $\mathcal{O}(\log n)$$\mathcal{O}(\log n)$$\mathcal{O}(\log n)$

Z nad wielkości coreset, można wykonać wyszukiwanie binarne dla każdego punktu n ⋅ ( 1 + ε ) - j , aby określić jego masy, co jest liczbą punktów pomiędzy a n ⋅ ( 1 + ε ) - j i$\mathcal{O}(\log n)$$a_n \cdot (1+\varepsilon)^{-j}$$a_n \cdot (1+\varepsilon)^{-j}$$a_n \cdot (1+\varepsilon)^{-(j+1)}$$\mathcal{O}((\log n)^2)$