Parallel algorithms for select and partition with noisy comparisons
From MaRDI portal
Publication:5361885
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
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
