Somme approximative d'une liste triée

Récemment, j'ai travaillé sur le problème du calcul de la somme approximative d'une liste de nombres non négatifs triés. Pour tout fixe , un schéma d'approximation du temps a été dérivé de telle sorte qu'il donne une approximation pour la somme. Le document est publié sur http://arxiv.org/abs/1112.0520 , qui n'a pas été finalisé.O ( log n ) ( 1 + ϵ $\epsilon>0$$O(\log n)$$(1+\epsilon)$

Je cherchais des travaux existants pour ce problème, mais je n'ai reçu que quelques articles liés à distance et les ai cités. Ce problème a-t-il été étudié auparavant? Si quelqu'un connaît des recherches existantes sur ce problème, faites-le moi savoir. J'apprécierai l'aide et mettrai à jour les citations en conséquence. Si les résultats sont anciens, le papier sera jeté dans une poubelle.

Ce problème est résolu dans le document suivant, où les problèmes plus généraux sont principalement traités: http://valis.cs.uiuc.edu/~sariel/papers/06/integrate/ .

Après avoir lu les détails de la preuve du papier du coreset de Har-Peled , je comprends maintenant que sa méthode implique un algorithme de temps O (log n) pour la somme approximative des nombres non négatifs triés. Le coreset est formé par un sous-ensemble de nombres dans la liste triée, et leurs positions ne dépendent que de la taille de la liste n et du rapport d'approximation epsilon. Les poids de tous les points du coreset sont calculables en temps O (log n). Ainsi, il apporte un algorithme de temps O (log n) pour la somme approximative d'une liste triée bien qu'il ne soit pas clairement revendiqué dans l'article. Comme l'algorithme est caché dans la preuve de la construction du coreset au lieu des théorèmes revendiqués de l'article de Har-Peled, je n'ai pas vu une telle conclusion juste après avoir vérifié les résultats dans l'article.

J'ai révisé mon article en supprimant la section 4 qui contient un algorithme de temps O (log n). L'article de Har-Peled est cité dans la version mise à jour. Le premier algorithme est toujours conservé car il a une complexité incomparable avec le temps O (log n). Par exemple, il s'exécute en temps O (log log n) lorsque les nombres dans la liste triée en entrée sont compris entre 0 et (log n) ^ {O (1)}. L'algorithme est basé sur une recherche de région quadratique, qui est très différente de la construction du coreset. Les bornes inférieures de temps sont également conservées, mais légèrement révisées.

Maintenant, j'ai une meilleure idée des œuvres de cette ligne. J'apprécie vraiment l'aide professionnelle des collègues théoriciens en informatique de ce site Web, qui fournit une excellente rétroaction. Mon article révisé sera disponible sur le même site d'archives dans les prochains jours. Je me réjouis sincèrement de tout autre commentaire sur des références connexes qui pourraient manquer.

Bin Fu

L'article de coreset de Har-Peled montre l'existence d'un coreset de pour le problème de somme approximative. Cela semble trivial et n'implique pas clairement aucun algorithme de temps pour le problème de somme approximative.$\mathcal{O}(\log n)$$\mathcal{O}(\log n)$

Supposons que . c'est réglé. Pour une liste triée , les points suivants forment un coreset trivial pour le problème de somme approximative:$\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}$

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

La contribution principale du papier de somme approximative est une méthode temporelle non mathématique pour trouver un coreset de taille , qui est différente de la construction ci-dessus. Ainsi, il apporte un algorithme temporel .O ( log n ) O ( log n $\mathcal{O}(\log n)$$\mathcal{O}(\log n)$$\mathcal{O}(\log n)$

Avec le coreset de taille dessus, on peut faire une recherche binaire pour chaque point pour déterminer son poids, qui est le nombre de points entre et dans la liste triée. Cela implique un algorithme temporel trivial pour le problème de somme approximative.a n ⋅ ( 1 + ε ) - j a n ⋅ ( 1 + ε ) - j a n ⋅ ( 1 + ε ) - ( j + 1 ) O ( ( log n ) 2$\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)$