Perkiraan jumlah daftar yang diurutkan

Baru-baru ini, saya bekerja pada masalah untuk menghitung perkiraan jumlah daftar nomor non-negatif yang diurutkan. Untuk setiap tetap , sebuah O ( log n ) skema pendekatan waktu yang telah diturunkan sedemikian rupa sehingga memberikan ( 1 + ε ) -approximation untuk penjumlahan. Makalah ini diposting di http://arxiv.org/abs/1112.0520 , yang belum selesai.$\epsilon>0$$O(\log n)$$(1+\epsilon)$

Saya telah mencari karya yang ada untuk masalah ini, tetapi saya hanya mendapat beberapa makalah terkait dari jauh, dan mengutipnya. Apakah masalah ini dipelajari sebelumnya? Jika seseorang mengetahui penelitian yang ada tentang masalah ini, beri tahu saya. Saya akan menghargai bantuannya, dan memperbarui kutipan yang sesuai. Jika hasilnya sudah tua, kertas itu akan dibuang ke tong sampah.

Masalah ini diselesaikan dalam makalah berikut, di mana masalah yang lebih umum sebagian besar ditangani: http://valis.cs.uiuc.edu/~sariel/papers/06/integrate/ .

Setelah membaca rincian bukti dari kertas coreset Har-Peled , sekarang saya mengerti bahwa metodenya menyiratkan algoritma waktu O (log n) untuk perkiraan jumlah angka nonnegatif yang diurutkan. Coreset dibentuk oleh subset angka dalam daftar yang disortir, dan posisi mereka hanya bergantung pada ukuran daftar n dan rasio pendekatan epsilon. Bobot semua titik dalam coreset dapat dihitung dalam waktu O (log n). Dengan demikian, ia membawa algoritma waktu O (log n) untuk perkiraan jumlah daftar yang disortir meskipun tidak secara jelas diklaim dalam makalah. Karena algoritme tersembunyi dalam bukti konstruksi coreset alih-alih teorema yang diklaim makalah Har-Peled, saya tidak melihat kesimpulan seperti itu setelah memeriksa hasil di kertas.

Saya telah merevisi makalah saya dengan menghapus bagian 4 yang berisi algoritma waktu O (log n). Makalah Har-Peled dikutip dalam versi terbaru. Algoritma pertama masih disimpan karena memiliki kompleksitas yang tak tertandingi dengan waktu O (log n). Misalnya, ini berjalan dalam waktu O (log log n) ketika angka-angka dalam daftar diurutkan input berada dalam kisaran dari 0 hingga (log n) ^ {O (1)}. Algoritma ini didasarkan pada pencarian wilayah kuadratik, yang sangat berbeda dari konstruksi coreset. Batas waktu yang lebih rendah juga dipertahankan, tetapi sedikit direvisi.

Sekarang saya punya ide yang lebih baik tentang karya-karya di baris ini. Saya benar-benar menghargai bantuan profesional dari rekan-rekan ilmu komputer teoretis di situs web ini, yang memberikan umpan balik yang sangat baik. Makalah yang saya revisi akan tersedia di situs arsip yang sama dalam beberapa hari ke depan. Saya dengan tulus menyambut komentar lebih lanjut tentang referensi terkait yang mungkin terlewatkan.

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