Persyaratan penyimpanan untuk pemilihan median (algoritma dua lintasan)

Dalam sebuah makalah klasik Munro dan Paterson mempelajari masalah berapa banyak penyimpanan yang diperlukan untuk suatu algoritma untuk menemukan median dalam array yang diurutkan secara acak. Secara khusus mereka fokus pada model berikut:

input dibaca dari kiri ke kanan untuk sejumlah P kali.

Terlihat bahwa sel-sel memori cukup, tetapi batas bawah yang sesuai hanya diketahui untuk P = 1. Saya belum melihat hasil apa pun untuk P> 1. Adakah yang tahu tentang batas bawah seperti itu? $O(n^{\frac{1}{2P}})$

Perhatikan bahwa kesulitan utama di sini adalah bahwa pada pass kedua input tidak dipesan secara acak lagi.

Coba makalah ini oleh Chan dalam SODA baru-baru ini: http://portal.acm.org/citation.cfm?id=1721842&dl=ACM .

Pencarian Google cepat juga menemukan makalah berikut yang terlihat mungkin relevan, tetapi saya belum membacanya: http://portal.acm.org/citation.cfm?id=1374470 .

Makalah pertama yang membuktikan batasan untuk lebih dari 1 pass adalah makalah saya dengan Jayram dan Amit dari SODA'08. Lalu ada makalah yang disebutkan Warren, yang meningkatkan batas dengan bukti yang lebih bersih.

Singkatnya, kami memahami ketergantungan jika Anda mengizinkan konstanta di depan jumlah lintasan. Tentu saja, konstanta ini berada dalam eksponen, sehingga Anda dapat meminta pemahaman yang tepat. Keluhan utama saya adalah bahwa model multi-aliran tidak termotivasi dengan baik.

Pertanyaan yang lebih menarik adalah apakah kita bisa membuktikan program percabangan batas bawah. Mungkinkah bahkan untuk algoritma ruang terbatas yang dapat mengakses memori sesuka hati, strategi terbaik adalah dengan hanya melakukan multipass streaming?

Jawabannya tampaknya afirmatif, dan kami memiliki beberapa kemajuan untuk membuktikannya.