Finding an approximate median with high probability in constant parallel time

DOI10.1016/0020-0190(90)90140-SMaRDI QIDQ911292zbMATH OpenOpenAlexFDO

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

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)

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

Cites work

• An optimally efficient selection algorithm

Cited in

(10)

• A parallel median algorithm
• Finding the Median (Obliviously) with Bounded Space
• 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
• scientific article; zbMATH DE number 437531 (Why is no real title available?)
• 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)