Time bounds for selection

DOI10.1016/S0022-0000(73)80033-9zbMath0278.68033OpenAlexW1996641400WikidataQ55881151 ScholiaQ55881151MaRDI QIDQ1394121

Manuel Blum, 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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) General topics in the theory of software (68N01) Algorithms in computer science (68W99)

Related Items

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, Multiprocessor extensions to real-time calculus, Maintenance of configurations in the plane, Parallel selection, The complexity of selection and ranking in X+Y and matrices with sorted columns, Weighted median algorithms for $L_ 1$ approximation, An optimal boundary fair scheduling algorithm for multiprocessor real-time systems, Bin packing can be solved within 1+epsilon in linear time, The saga of minimum spanning trees, An algorithm for a singly constrained class of quadratic programs subject upper and lower bounds, A generalized boxplot for skewed and heavy-tailed distributions, A note on upper bounds for the selection problem, Weight-constrained and density-constrained paths in a tree: enumerating, counting, and $k$-maximum density paths, Hyperbolic 0-1 programming and query optimization in information retrieval, On two-machine flow shop scheduling, A linear algorithm for bisecting a polygon, Optimal parallel selection in sorted matrices, Selection from read-only memory and sorting with minimum data movement, Finding the minimum number of elements with sum above a threshold, QuickHeapsort: modifications and improved analysis, Finding a non-minority ball with majority answers, Finding the $k$ smallest spanning trees, Necklaces, convolutions, and $X+Y$, Matching points with rectangles and squares, Geometric medians, A heuristic for preemptive scheduling with set-up times, Fast algorithm for multicast and data gathering in wireless networks, Simple bounds on the convergence rate of an ergodic Markov chain, Relaxed voting and competitive location under monotonous gain functions on trees, Applying fuzzy weighted average approach to evaluate office layouts with Feng-shui consideration, Improved algorithms for the continuous tree edge-partition problems and a note on ratio and sorted matrices searches, The median and its extensions, On sorting, heaps, and minimum spanning trees, An $0(| E|\log\log| V|)$ algorithm for finding minimum spanning trees, Cache-oblivious selection in sorted $X+Y$ matrices, Finding the median, Refined complexity analysis for heap operations, On an optimization problem with nested constraints, Algebraic optimization: The Fermat-Weber location problem, Speeding up dynamic programming in the line-constrained $k$-median, Sorting by distributive partitioning, A linear selection algorithm for sets of elements with weights, Region-restricted clustering for geographic data mining, A faster polynomial algorithm for the unbalanced Hitchcock transportation problem, A linear time algorithm for the weighted lexicographic rectilinear 1-center problem in the plane, Selection from read-only memory with limited workspace, On some geometric selection and optimization problems via sorted matrices, Geometric quadrisection in linear time, with application to VLSI placement, Exponential bounds for the running time of a selection algorithm, Selection in $X+Y$ and matrices with sorted rows and columns, Geometric applications of posets, Optimal layout of edge-weighted forests, Randomized selection in $n+C+o(n)$ comparisons, Robust economic order quantity models, NP-hard and linear variants of hypergraph partitioning, Restricted center problems under polyhedral gauges, Multivariate analysis of orthogonal range searching and graph distances, A linear-time algorithm for the bottleneck transportation problem with a fixed number of sources, Analysis of a linear programming heuristic for scheduling unrelated parallel machines, A linear time bin-packing algorithm, On characteristics of ancestral character-state reconstructions under the accelerated transformation optimization, A fast algorithm for the rectilinear distance location problem, Selecting distances in the plane, Splitting a configuration in a simplex, Min-energy voltage allocation for tree-structured tasks, Finding the Median (Obliviously) with Bounded Space, Improved algorithms for some competitive location centroid problems on paths, trees and graphs, ParILUT---A New Parallel Threshold ILU Factorization, Near-optimal online multiselection in internal and external memory, Comment: Monitoring networked applications with incremental quantile estimation, Extensions to the Weber problem, Space-Efficient Frameworks for Top- k String Retrieval, Roll cutting in the curtain industry, or: a well-solvable allocation problem, Transforming pseudo-triangulations, Extreme point and halving edge search in abstract order types, Optimal robust mean and location estimation via convex programs with respect to any pseudo-norms, String indexing for top-$k$ close consecutive occurrences, Fast deterministic selection on mesh-connected processor arrays, Finding the $\alpha n$-th largest element, Algorithms for proximity problems in higher dimensions, Three-dimensional axial assignment problems with decomposable cost coefficients, Proportionate progress: A notion of fairness in resource allocation, The $k$-metric dimension, Encodings of Range Maximum-Sum Segment Queries and Applications, Optimizing Squares Covering a Set of Points, A fast algorithm for quadratic resource allocation problems with nested constraints, Partial sorting problem on evolving data, Linear-time fitting of a $k$-step function, The optimal solution set of the multi-source Weber problem, Pinning Balloons with Perfect Angles and Optimal Area, Maximizing single attribute diversity in group selection, Minimum variance allocation among constrained intervals, Decomposable multi-parameter matroid optimization problems., A tight linear time $\frac{13}{12}$-approximation algorithm for the $P2 || C_{\max}$ problem, Cardinality constrained connected balanced partitions of trees under different criteria, A linear time approximation scheme for computing geometric maximum $k$-star, On mean estimation for heteroscedastic random variables, Ham-sandwich cuts for abstract order types, Lattice-theoretic properties of MPR-posets in phylogeny, Computing square roots of trivially perfect and threshold graphs, On total $f$-domination: polyhedral and algorithmic results, A survey on the continuous nonlinear resource allocation problem, A linear time algorithm for the robust recoverable selection problem, Finding a given number of solutions to a system of fuzzy constraints, DC formulations and algorithms for sparse optimization problems, Optimizing squares covering a set of points, STRONGER QUICKHEAPS, Computational aspects of the colorful Carathéodory theorem, Building fences straight and high: an optimal algorithm for finding the maximum length you can cut $k$ times from given sticks, Tardiness bounds under global EDF scheduling on a multiprocessor, Complexity and algorithms for nonlinear optimization problems, Minimax trees in linear time with applications, Reoptimization in Lagrangian methods for the $0$-$1$ quadratic knapsack problem, Worst-case ratios of networks in the rectilinear plane, A simple linear algorithm for computing rectilinear 3-centers, Hybrid rounding techniques for knapsack problems, On partial sorting in restricted rounds, Resource allocation problems in decentralized energy management, New space/time tradeoffs for top-$k$ document retrieval on sequences, Scheduling on semi-identical processors, Balanced vertex-orderings of graphs, On $f$-domination: polyhedral and algorithmic results, Multi-dimensional tree guided efficient global association for decomposition-based evolutionary many-objective optimization, Calibrated model-based evidential clustering using bootstrapping, Weighted selectin for the multiset x∓xwith application to r–estimates and associated confidence limits, Algorithms for Problems on Maximum Density Segment, A novel analytical integer optimization method for wavelet based subband coding, A (probably) optimal algorithm for \textsc{bisection} on bounded-treewidth graphs, Robust K-Median and K-means clustering algorithms for incomplete data, Sparse randomized shortest paths routing with Tsallis divergence regularization, Finding Mode Using Equality Comparisons, QuickXsort: a fast sorting scheme in theory and practice, Page-queries as a tool for organizing secondary memory auxiliary databases. II: Optimal selection of SADB contents, Fast algorithms for convex cost flow problems on circles, lines, and trees, No-collision transportation maps, Speeding up Dynamic Programming in the Line-Constrained k-median, SOBRA - Shielding Optimization for BRAchytherapy, Dividing splittable goods evenly and with limited fragmentation, Upper and lower degree-constrained graph orientation with minimum penalty, A selectable sloppy heap, A new linear storage, polynomial-time approximation scheme for the subset-sum problem, Open questions concerning Weiszfeld's algorithm for the Fermat-Weber location problem, Approximation algorithms for knapsack problems with cardinality constraints, Continuous bottleneck tree partitioning problems, Algorithms for the parallel alternating direction access machine, Heaps and heapsort on secondary storage, Linear sorting with O(log n) processors, On uniform $k$-partition problems, Computing (and Life) Is All about Tradeoffs, Generating most parsimonious reconstructions on a tree: A generalization of the Farris-Swofford-Maddison method, Non-convex exact community recovery in stochastic block model, Comparator networks for binary heap construction, On Floyd and Rivest's SELECT algorithm, Finding median in read-only memory on integer input, ALGORITHMS FOR K-DISJOINT MAXIMUM SUBARRAYS, On the planar two-center problem and circular hulls, A structured family of clustering and tree construction methods, Selecting small ranks in EREW PRAM, Selection by rank inK-dimensional binary search trees, A sample efficient sparse FFT for arbitrary frequency candidate sets in high dimensions

Uses Software

Find

Cites Work