Suma aproximada de una lista ordenada

Recientemente, trabajé en el problema para calcular la suma aproximada de una lista de números no negativos ordenados. Para cualquier fijo , un O ( log n ) esquema de aproximación tiempo se ha derivado de tal manera que da una ( 1 + ε ) : Aproximación para la suma. El documento se publica en$\epsilon>0$$O(\log n)$$(1+\epsilon)$ http://arxiv.org/abs/1112.0520 , que no se ha finalizado.

He estado buscando trabajos existentes para este problema, pero solo obtuve algunos documentos relacionados de forma remota y los cité. ¿Se estudió este problema antes? Si alguien conoce alguna investigación existente sobre este problema, hágamelo saber. Apreciaré la ayuda y actualizaré las citas en consecuencia. Si los resultados son viejos, el papel será arrojado a un bote de basura.

Este problema se resuelve en el siguiente documento, donde se abordan principalmente problemas más generales: http://valis.cs.uiuc.edu/~sariel/papers/06/integrate/ .

Después de leer los detalles de prueba de Har-Peled , ahora entiendo que su método implica un algoritmo de tiempo O (log n) para la suma aproximada de números no negativos ordenados. El núcleo está formado por un subconjunto de números en la lista ordenada, y sus posiciones solo dependen del tamaño de la lista n y la relación de aproximación epsilon. Los pesos de todos los puntos en el núcleo son computables en el tiempo O (log n). Por lo tanto, trae un algoritmo de tiempo O (log n) para la suma aproximada de una lista ordenada, aunque no se afirma claramente en el documento. Como el algoritmo está oculto en la prueba de la construcción del núcleo en lugar de los teoremas del documento de Har-Peled, no vi tal conclusión justo después de verificar los resultados en el documento.

Revisé mi trabajo eliminando la sección 4 que contiene un algoritmo de tiempo O (log n). El artículo de Har-Peled se cita en la versión actualizada. El primer algoritmo aún se mantiene ya que tiene una complejidad incomparable con el tiempo O (log n). Por ejemplo, se ejecuta en tiempo O (log log n) cuando los números en la lista ordenada de entrada están en el rango de 0 a (log n) ^ {O (1)}. El algoritmo se basa en una búsqueda de región cuadrática, que es muy diferente de la construcción del núcleo. Los límites inferiores de tiempo también se mantienen, pero se revisan ligeramente.

Ahora tengo una mejor idea sobre los trabajos en esta línea. Realmente aprecio la ayuda profesional de los colegas teóricos de informática en este sitio web, que proporciona una excelente respuesta. Mi artículo revisado estará disponible en el mismo sitio de archivo en los próximos días. Agradezco sinceramente más comentarios sobre referencias relacionadas que podrían perderse.

Bin Fu

El documento del núcleo de Har-Peled muestra la existencia de un núcleo de tamaño para el problema de la suma aproximada. Esto parece trivial y no implica claramente ningún O ( log n $\mathcal{O}(\log n)$$\mathcal{O}(\log n)$ algoritmo de tiempo para el problema de la suma aproximada.

$\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)$ algoritmo de tiempo .

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