Parallel algorithms for select and partition with noisy comparisons

DOI10.1145/2897518.2897642zbMath1375.68186arXiv1603.04941OpenAlexW2301054524MaRDI QIDQ5361885

Mark Braverman, S. Matthew Weinberg, Jieming Mao

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

parallel algorithmsrank aggregationmedian findingnoisy comparisonstop-\(K\)

Mathematics Subject Classification ID

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

Related Items (10)

Skyline Computation with Noisy Comparisons ⋮ An Optimal Approximation for Submodular Maximization Under a Matroid Constraint in the Adaptive Complexity Model ⋮ Unnamed Item ⋮ Algorithms for cardinality-constrained monotone DR-submodular maximization with low adaptivity and query complexity ⋮ Unnamed Item ⋮ On the multi-interval Ulam-Rényi game: for 3 lies 4 intervals suffice ⋮ Approximate minimum selection with unreliable comparisons ⋮ Unnamed Item ⋮ An adaptive algorithm for maximization of non-submodular function with a matroid constraint ⋮ Asymptotically Optimal Sequential Design for Rank Aggregation

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