Finding an approximate median with high probability in constant parallel time

DOI10.1016/0020-0190(90)90140-SzbMATH Open0696.68070OpenAlexW1997347990MaRDI QIDQ911292FDOQ911292

Authors: Sandeep Sen 

Publication date: 1990

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(90)90140-s

Recommendations

• A parallel median algorithm
• Parallel selection
• Probabilistic Parallel Algorithms for Sorting and Selection
• An improved, randomized algorithm for parallel selection with an experimental study
• Parallel comparison algorithms for approximation problems

zbMATH Keywords

computational complexityanalysis of algorithmscombinatorial problemsCRCW PRAM

Mathematics Subject Classification ID

Enumerative combinatorics (05A99) Analysis of algorithms and problem complexity (68Q25) Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming) (90C33) Complexity of computation (including implicit computational complexity) (03D15)

Cites Work

• An optimally efficient selection algorithm

Cited In (10)

• Finding the Median (Obliviously) with Bounded Space
• A parallel median algorithm
• Median bounds and their application
• Efficient randomized algorithms for the repeated median line estimator
• Fast randomized parallel methods for planar convex hull construction
• An improved, randomized algorithm for parallel selection with an experimental study
• On ``An improved algorithm for finding the median distributively
• Parallel Selection with High Probability
• Title not available (Why is that?)
• Lightweight approximate selection

This page was built for publication: Finding an approximate median with high probability in constant parallel time

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