Time bounds for selection
From MaRDI portal
Publication:1394121
DOI10.1016/S0022-0000(73)80033-9zbMath0278.68033OpenAlexW1996641400WikidataQ55881151 ScholiaQ55881151MaRDI QIDQ1394121
Robert W. Floyd, Ronald L. Rivest, Vaughan R. Pratt, Robert Endre Tarjan
Publication date: 1973
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0022-0000(73)80033-9
Analysis of algorithms and problem complexity (68Q25) General topics in the theory of software (68N01) Algorithms in computer science (68W99)
Related Items (only showing first 100 items - show all)
Maximum likelihood estimation of cell probabilities in constrained multinomial models ⋮ On the median-of-k version of Hoare's selection algorithm ⋮ Light graphs with small routing cost ⋮ Select with Groups of 3 or 4 ⋮ Selection and sorting in totally monotone arrays ⋮ A Linear Time Algorithm for Ordered Partition ⋮ Progress in selection ⋮ On condorcet and median points of simple rectilinear polygons ⋮ Finding the k smallest spanning trees ⋮ Selection in monotone matrices and computing k th nearest neighbors ⋮ Optimization of algorithm estimation of certain probabilistic characteristics ⋮ Multidimensional binary partitions: distributed data structures for spatial partitioning ⋮ Optimal Parallel Algorithms For Multiselection On Mesh-Connected Computers ⋮ A general lower bound on the I/O-complexity of comparison-based algorithms ⋮ Efficient calculation of hodges-lehmann estimators of location ⋮ Sorting Short Keys in Circuits of Size ${o(n \log n)}$ ⋮ Coarse Grained Parallel Selection ⋮ On a Reduction for a Class of Resource Allocation Problems ⋮ Geometric Applications of Posets ⋮ Ranked Document Retrieval in External Memory ⋮ Integer knapsack problems with profit functions of the same value range ⋮ Min‐sum controllable risk problems with concave risk functions of the same value range ⋮ Stochastic coordination in heterogeneous load balancing systems ⋮ Discrete Fréchet distance for closed curves ⋮ On the lower bound for minimum comparison selection ⋮ Homogeneous and Non-homogeneous Algorithms ⋮ A simple and fast linear-time algorithm for divisor methods of apportionment ⋮ Estimating Optimal Infinite Horizon Dynamic Treatment Regimes via pT-Learning ⋮ New Upper Bounds on Continuous Tree Edge-Partition Problem ⋮ Faster first-order primal-dual methods for linear programming using restarts and sharpness ⋮ Approximating the smallest \(k\)-enclosing geodesic disc in a simple polygon ⋮ Dörfler marking with minimal cardinality is a linear complexity problem ⋮ Unnamed Item ⋮ Range Medians ⋮ Single-Source Bottleneck Path Algorithm Faster than Sorting for Sparse Graphs. ⋮ A geometrical method in combinatorial complexity ⋮ On Fixed Point Theory in Partially Ordered (Quasi-)metric Spaces and an Application to Complexity Analysis of Algorithms ⋮ Neural Simpletrons: Learning in the Limit of Few Labels with Directed Generative Networks ⋮ Selection in the Presence of Memory Faults, with Applications to In-place Resilient Sorting ⋮ Two-variable linear programming in parallel ⋮ The \(k\)-centrum multi-facility location problem ⋮ A Multilevel Adaptive Reaction-splitting Simulation Method for Stochastic Reaction Networks ⋮ Unnamed Item ⋮ On some geometric selection and optimization problems via sorted matrices ⋮ Sorting multisets stably in minimum space ⋮ Gathering in the plane of location-aware robots in the presence of spies ⋮ Two-variable linear programming in parallel ⋮ Comparator networks for binary heap construction ⋮ Greedy Strategy Works for k-Center Clustering with Outliers and Coreset Construction ⋮ Cascade heap: towards time-optimal extractions ⋮ Cascade heap: towards time-optimal extractions ⋮ Finding a mediocre player ⋮ Selection Algorithms with Small Groups ⋮ Finding Least-Distances Lines ⋮ Parallel bucket sorting on graphics processing units based on convex optimization ⋮ A Forward-Backward Single-Source Shortest Paths Algorithm ⋮ Polynomially bounded algorithms for locatingp-centers on a tree ⋮ Dividing splittable goods evenly and with limited fragmentation ⋮ An $O ( ( n\log p )^2 )$ Algorithm for the Continuous p-Center Problem on a Tree ⋮ Efficient algorithms for robustness in resource allocation and scheduling problems ⋮ Dynamic layers of maxima with applications to dominating queries ⋮ Algorithms for parallel memory, I: Two-level memories ⋮ Online production planning to maximize the number of on-time orders ⋮ Sorting multisets stably in minimum space ⋮ Two new methods for constructing double-ended priority queues from priority queues ⋮ Fast projection onto the simplex and the \(l_1\) ball ⋮ Dynamic range majority data structures ⋮ The connected \(p\)-median problem on block graphs ⋮ Incomplete generalized \(L\)-statistics ⋮ An improved algorithm for finding the median distributively ⋮ Upper bounds for time-space trade-offs in sorting and selection ⋮ Bicriteria and restricted 2-facility Weber problems ⋮ Efficient selection on a binary tree ⋮ Batch RSA ⋮ Distributed algorithms for selection in sets ⋮ L-infinity interdistance selection by parametric search ⋮ Optimal parallel selection has complexity O(log log N) ⋮ Approximation algorithms for maximum dispersion ⋮ A more efficient algorithm for MPR problems in phylogeny ⋮ The algorithmic use of hypertree structure and maximum neighbourhood orderings ⋮ An approximation scheme for strip packing of rectangles with bounded dimensions ⋮ A Bayesian approach to relevance in game playing ⋮ Space-efficient geometric divide-and-conquer algorithms ⋮ Randomized algorithm for the sum selection problem ⋮ Illumination by floodlights ⋮ Preemptive scheduling of independent jobs on identical parallel machines subject to migration delays ⋮ Reprint of: Extreme point and halving edge search in abstract order types ⋮ Faster output-sensitive skyline computation algorithm ⋮ Proximal alternating linearized minimization for nonconvex and nonsmooth problems ⋮ On computing an optimal permutation of ranks for multiselection ⋮ Determining the mode ⋮ Architecture independent parallel selection with applications to parallel priority queues ⋮ Average-case complexity of the min-sum matrix product problem ⋮ Selection by distributive partitioning ⋮ Polynomial time algorithms for three-label point labeling. ⋮ New algorithms on wavelet trees and applications to information retrieval ⋮ Computing of high breakdown regression estimators without sorting on graphics processing units ⋮ Efficient searching using partial ordering ⋮ Minimizing the error of linear separators on linearly inseparable data ⋮ Coverage restricted to an angle
Uses Software
Cites Work
This page was built for publication: Time bounds for selection
