Vi anser att problemet med att hitta k th högsta element i en helt ordnad uppsättning n element (Select), och partitionera en helt ordnad uppsättning i den övre k och nedre n - k element (Partition) med parvis jämförelser. Motiverad av inställningar som peer grading eller crowdsourcing, där flera omgångar av interaktion är dyra och ifrågasatta jämförelser kan vara oförenliga med marken sanningen, utvärderar vi algoritmer baserade både på deras totala körtid och antalet interaktiva omgångar i tre jämförelsemodeller: ljudlös (där jämförelserna är korrekta), radering (där jämförelser raderas med sannolikhet 1 − γ), och bullriga (där jämförelser är korrekta med sannolikhet 1/2 + γ/2 och felaktiga annars). Vi erbjuder många matchande övre och nedre gränser i alla tre modellerna. Även våra resultat i den ljudlösa modellen, som är ganska välstuderad i TCS-litteraturen på parallella algoritmer, är nya.
I ett nyligen utfört arbete REF, Braverman, Mao och Weinberg studerade den runda komplexiteten i urvalet och få top-k och bottom-k element när crowd svar är alla korrekta, eller är felaktiga med sannolikhet 1 2 - λ 2, eller raderas med sannolikhet 1 - λ, för vissa λ > 0.
Parallel algorithms for select and partition with noisy comparisons
{'venue': 'STOC 2016', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}