Space-approximation Trade-off

14

Dalam makalah mereka Perkiraan Jarak Orakel , Thorup dan Zwick menunjukkan bahwa untuk setiap grafik tanpa arahan tertimbang, adalah mungkin untuk membangun struktur data ukuran yang dapat mengembalikan ( 2 k - 1 ) -approximate jarak antara setiap pasangan simpul dalam grafik.HAI(kn1+1/k)(2k-1)

Pada tingkat mendasar, konstruksi ini mencapai trade-off perkiraan ruang --- seseorang dapat mengurangi persyaratan ruang dengan biaya "kualitas" solusi yang lebih rendah.

Apa masalah grafik lain yang menunjukkan trade-off antara ruang dan perkiraan?

Saya tertarik pada kasus grafik statis dan dinamis, tertimbang dan tidak berbobot, tidak terarah, dan terarah.

Terima kasih.

ds.algorithms graph-theory approximation-algorithms space-complexity Rachit
sumber
Pertukaran biasanya berarti batas bawah: jika Anda membuat satu hal lebih kecil, maka yang lain harus lebih besar. Apakah Anda menginginkan hasil batas atas (seperti pada contoh Anda), atau hasil batas bawah?
Yoshio Okamoto
1
@YoshioOkamoto - Batas atas dapat "mencapai" trade-off --- batas atas tidak berarti bahwa trade-off itu penting (yang merupakan pertanyaan batas bawah), tetapi dapat mencapai satu. Apakah itu benar? Terlepas dari itu, saya tertarik pada batas bawah dan batas atas.
Rachit

Jawaban:

-2

penelitian ini tampaknya aktif dalam arti yang lebih terapan daripada teori yang Anda sebutkan (yaitu oracle dll) dengan algoritma "data streaming" yang berusaha untuk bekerja dengan data yang sangat besar melalui "jendela geser", dengan banyak algoritma grafik dipertimbangkan, tetapi memang relatif baru / baru-baru ini, cocok dengan arahan penelitian "data besar" .

Kami telah menemukan beberapa algoritma untuk masalah grafik mendasar dalam model W-Stream, termasuk komponen yang terhubung, pohon spanning minimum, komponen yang tidak terhubung dan jalur terpendek satu sumber. Sejauh pengetahuan kami, algoritma kami adalah yang pertama yang memungkinkan ruang efektif / melewati pengorbanan untuk masalah seperti itu dalam pengaturan streaming data.

referensi ini termasuk referensi / survei lain yang mungkin bisa membantu.

Terlepas dari pembatasan berat yang diberlakukan oleh model [streaming klasik], kesuksesan besar telah dicapai untuk beberapa masalah sketsa data dan statistik, di mana jumlah lintasan yang terus-menerus dan memori kerja polylogaritmik telah terbukti cukup untuk menemukan solusi perkiraan (lihat [4, 16, 17] dan bibliografi yang luas dalam [7, 29]).

juga:

vzn
sumber