An efficient algorithm for the approximate median selection problem

DOI10.1007/3-540-46521-9_19MaRDI QIDQ2728905zbMATH OpenFDO

Authors Sebastiano Battiato, Domenico Cantone, Dario Catalano, Gianluca Cincotti, Micha Hofri

Publication date 4 November 2001

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-46521-9_19

zbMATH Keywords

analysis of algorithmsapproximation algorithmsin-place algorithmsmedian selection

Mathematics Subject Classification ID

Computing methodologies and applications (68U99) Approximation algorithms (68W25) Analysis of algorithms (68W40)

Recommendations

• Linear-time in-place selection in less than 3n comparisons
• Further analysis of the remedian algorithm
• Faster, Space-Efficient Selection Algorithms in Read-Only Memory for Integers
• Finding median in read-only memory on integer input
• Selecting the Median

Cited in

(13)

• Efficient algorithms for approximate smooth selection
• A selectable sloppy heap
• On lower bounds for selecting the median
• Lightweight approximate selection
• Select with groups of 3 or 4
• Further analysis of the remedian algorithm
• scientific article; zbMATH DE number 1974052 (Why is no real title available?)
• Finding the minimum number of elements with sum above a threshold
• Selection Algorithms with Small Groups
• The shifting sands algorithm
• Simplified implementation of the recursive median sieve
• scientific article; zbMATH DE number 7765400 (Why is no real title available?)
• Asymptotics of wide remedians

This page was built for publication: An efficient algorithm for the approximate median selection problem

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