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. $\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.

ds.algorithms reference-request

— Bin Fu
źródło

Dziękujemy za udostępnienie artykułu! Czy mógłby Pan uzasadnić, dlaczego warto przestudiować przybliżony problem sumy dla posortowanych list? To znaczy założenie, że lista jest posortowana, jest dość silnym założeniem.

— Dai Le

@DaiLe: przypuszczalnie dlatego, że założenie dodaje sporo struktury do problemu; próba znalezienia przybliżonej sumy nieposortowanej listy jest oczywiście trudna, ponieważ nie masz absolutnie żadnych informacji o liście poza konkretnymi badanymi liczbami.

— Steven Stadnicki

@Bin: Dolna granica przybliżenia sumy w niezupełnie pozytywnym przypadku wydaje się pochodzić z „połowu”, że nie ma dobrego sposobu na przybliżenie zera; oczywiście jest to standardowy schemat aproksymacji, ale tutaj wydaje się, że lepiej byłoby zmierzyć błąd w kategoriach wielkości największego komponentu niż wielkości wynikowej sumy; czy to sprawia, że wyniki są trywialne?

— Steven Stadnicki

W matematyce często widzimy wzory do obliczania sum takich jak f (1) + f (2) +… + f (n), gdzie f (n) jest funkcją. Wiele funkcji jest monotonicznych. Na przykład f (n) = n ^ k (log n). Naturalne jest pytanie, czy istnieje skuteczny sposób obliczenia tego rodzaju sum dla funkcji monotonicznych f (.). Kiedy pisałem ten artykuł, miałem obawy, że tracę czas na robienie czegoś, co może być już znane. Właśnie dlatego przyszedłem na tę stronę, aby poprosić o pomoc w sprawie referencji, ponieważ jest tu wielu profesjonalnych ludzi. Dziękuję za komentarze. Bin Fu

— Bin Fu,

@Bin Fu: Dziękujemy za odpowiedź. Założenie ma sens!

— Dai Le

Odpowiedzi:

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

— Sariel Har-Peled
źródło

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

— Bin Fu
źródło

Ahem. Który z dziesięciu papierów Har-Peleda masz na myśli? Także rdzeń (z dwoma e) nie jest tym samym co gorset (z jednym e). Jeden używa losowego próbkowania; drugi wykorzystuje kości wieloryba.

— Jeffε

@ Jɛ ﬀ E: Myślę, że ma na myśli papier, o którym mowa w odpowiedzi Sariela.

— Tsuyoshi Ito

Być może, ale kiedy zamieściłem swój komentarz, odpowiedź była wyżej na stronie niż Sariel. Dodałem link.

— Jeffε

Moja zaktualizowana wersja jest teraz dostępna na arxiv.org/abs/1112.0520 .

— Bin Fu

-3

$\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 , aby określić jego masy, co jest liczbą punktów pomiędzy 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)$

— Bin Fu
źródło

Który z dziesięciu papierów Har- Peleda masz na myśli? Również coreset ≠ gorset !

— Jeffε

To nie powinno być zamieszczone jako odpowiedź, ponieważ w ogóle nie odpowiada na twoje pytanie. Byłoby najlepiej, gdyby mógł zostać opublikowany jako komentarz do odpowiedzi Sariela, ale jest na to za długo. Zamieszczę go jako aktualizację pytania.

— Tsuyoshi Ito

Tsuyoshi: Masz rację. Moje komentarze powinny zostać umieszczone na

— Bin Fu

pole komentarza zamiast obszaru odpowiedzi. Przepraszam.

— Bin Fu,

Nie sądzę, że rozumiesz mój artykuł. To, co napisałeś powyżej, jest złe, a nie to, co jest w mojej pracy.

— Sariel Har-Peled,