Parallel algorithms for select and partition with noisy comparisons

DOI10.1145/2897518.2897642MaRDI QIDQ5361885zbMATH OpenOpenAlexFDO

Authors Mark Braverman, Jieming Mao, S. Matthew Weinberg

Publication date 29 September 2017

Published in Proceedings of the forty-eighth annual ACM symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1603.04941

zbMATH Keywords

median findingnoisy comparisonsparallel algorithmsrank aggregationtop-\(K\)

Mathematics Subject Classification ID

Combinatorial probability (60C05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Parallel algorithms in computer science (68W10)

Abstract: We consider the problem of finding the $k^{th}$ highest element in a totally ordered set of $n$ elements (select), and partitioning a totally ordered set into the top $k$ and bottom $n-k$ elements (partition) using pairwise comparisons. Motivated by settings like peer grading or crowdsourcing, where multiple rounds of interaction are costly and queried comparisons may be inconsistent with the ground truth, we evaluate algorithms based both on their total runtime and the number of interactive rounds in three comparison models: noiseless (where the comparisons are correct), erasure (where comparisons are erased with probability $1-gamma$), and noisy (where comparisons are correct with probability $1/2+gamma/2$ and incorrect otherwise). We provide numerous matching upper and lower bounds in all three models. Even our results in the noiseless model, which is quite well-studied in the TCS literature on parallel algorithms, are novel.

Recommendations

• An efficient parallel algorithm for multiselection
• Parallel algorithms for partitioning sorted sets and related problems
• Parallel algorithms for partitioning sorted sets and related problems
• A parallel algorithm for subset selection
• An optimal parallel algorithm for the multiselection problem
• Probabilistic Parallel Algorithms for Sorting and Selection
• scientific article; zbMATH DE number 4082988
• scientific article; zbMATH DE number 4037239
• A parallel selection algorithm

Cited in

(16)

• Selection algorithms for parallel disk systems
• Approximate minimum selection with unreliable comparisons
• An adaptive algorithm for maximization of non-submodular function with a matroid constraint
• On the multi-interval Ulam-Rényi game: for 3 lies 4 intervals suffice
• Parallel Selection with High Probability
• Maximum selection and sorting with adversarial comparators
• Preference-based online learning with dueling bandits: a survey
• Top-k and clustering with noisy comparisons
• Skyline Computation with Noisy Comparisons
• An Optimal Approximation for Submodular Maximization Under a Matroid Constraint in the Adaptive Complexity Model
• Optimal sorting with persistent comparison errors
• Asymptotically Optimal Sequential Design for Rank Aggregation
• Algorithms for cardinality-constrained monotone DR-submodular maximization with low adaptivity and query complexity
• Approximate selection with unreliable comparisons in sublinear time
• Complexity of round-robin allocation with potentially noisy queries
• Complexity of round-robin allocation with potentially noisy queries

This page was built for publication: Parallel algorithms for select and partition with noisy comparisons

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5361885)