Time bounds for selection

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

Ronald L. Rivest, Robert Endre Tarjan, Vaughan R. Pratt, Manuel Blum, Robert W. Floyd

Publication date: 1973

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

68Q25: Analysis of algorithms and problem complexity

68N01: General topics in the theory of software

68W99: Algorithms in computer science

Related Items

Refined complexity analysis for heap operations, On an optimization problem with nested constraints, Algebraic optimization: The Fermat-Weber location problem, Optimal parallel selection in sorted matrices, Selection from read-only memory and sorting with minimum data movement, Exponential bounds for the running time of a selection algorithm, Selection in $X+Y$ and matrices with sorted rows and columns, Efficient algorithms for robustness in resource allocation and scheduling problems, Space-efficient geometric divide-and-conquer algorithms, Randomized algorithm for the sum selection problem, Parallel selection, Weighted median algorithms for $L_ 1$ approximation, An algorithm for a singly constrained class of quadratic programs subject upper and lower bounds, Matching points with rectangles and squares, 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, Analysis of a linear programming heuristic for scheduling unrelated parallel machines, A linear time bin-packing algorithm, An improved algorithm for finding the median distributively, Upper bounds for time-space trade-offs in sorting and selection, Efficient selection on a binary tree, Distributed algorithms for selection in sets, L-infinity interdistance selection by parametric search, Optimal parallel selection has complexity O(log log N), A Bayesian approach to relevance in game playing, Determining the mode, Selection by distributive partitioning, Efficient searching using partial ordering, Maintenance of configurations in the plane, The complexity of selection and ranking in X+Y and matrices with sorted columns, Bin packing can be solved within 1+epsilon in linear time, A note on upper bounds for the selection problem, Hyperbolic 0-1 programming and query optimization in information retrieval, A linear algorithm for bisecting a polygon, Finding the $k$ smallest spanning trees, Geometric medians, A heuristic for preemptive scheduling with set-up times, Simple bounds on the convergence rate of an ergodic Markov chain, An $0(| E|\log\log| V|)$ algorithm for finding minimum spanning trees, Finding the median, Sorting by distributive partitioning, A linear selection algorithm for sets of elements with weights, On some geometric selection and optimization problems via sorted matrices, Geometric applications of posets, Optimal layout of edge-weighted forests, Robust economic order quantity models, Restricted center problems under polyhedral gauges, A linear-time algorithm for the bottleneck transportation problem with a fixed number of sources, Algorithms for parallel memory, I: Two-level memories, Sorting multisets stably in minimum space, Incomplete generalized $L$-statistics, Bicriteria and restricted 2-facility Weber problems, Batch RSA, 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, Illumination by floodlights, Architecture independent parallel selection with applications to parallel priority queues, Polynomial time algorithms for three-label point labeling., Decomposable multi-parameter matroid optimization problems., Lattice-theoretic properties of MPR-posets in phylogeny, Approximation algorithms for knapsack problems with cardinality constraints, Algorithms for the parallel alternating direction access machine, Heaps and heapsort on secondary storage, Comparator networks for binary heap construction, A structured family of clustering and tree construction methods, Selecting small ranks in EREW PRAM, On characteristics of ancestral character-state reconstructions under the accelerated transformation optimization, Balanced vertex-orderings of graphs, Page-queries as a tool for organizing secondary memory auxiliary databases. II: Optimal selection of SADB contents, 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, Continuous bottleneck tree partitioning problems, Linear sorting with O(log n) processors, Generating most parsimonious reconstructions on a tree: A generalization of the Farris-Swofford-Maddison method, 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, Selecting distances in the plane, Splitting a configuration in a simplex, Min-energy voltage allocation for tree-structured tasks, Comment: Monitoring networked applications with incremental quantile estimation, A survey on the continuous nonlinear resource allocation problem, Tardiness bounds under global EDF scheduling on a multiprocessor, Complexity and algorithms for nonlinear optimization problems, A simple linear algorithm for computing rectilinear 3-centers, Hybrid rounding techniques for knapsack problems, On uniform $k$-partition problems, On Floyd and Rivest's SELECT algorithm, Roll cutting in the curtain industry, or: a well-solvable allocation problem, Worst-case ratios of networks in the rectilinear plane, Scheduling on semi-identical processors, Weighted selectin for the multiset x∓xwith application to r–estimates and associated confidence limits, ALGORITHMS FOR K-DISJOINT MAXIMUM SUBARRAYS, New Upper Bounds on Continuous Tree Edge-Partition Problem, Range Medians, On the median-of-k version of Hoare's selection algorithm, Light graphs with small routing cost, Optimal Parallel Algorithms For Multiselection On Mesh-Connected Computers, The $k$-centrum multi-facility location problem, Two-variable linear programming in parallel, Finding Least-Distances Lines, Optimization of algorithm estimation of certain probabilistic characteristics, Efficient calculation of hodges-lehmann estimators of location, Unnamed Item, Unnamed Item, Polynomially bounded algorithms for locatingp-centers on a tree, An $O ( ( n\log p )^2 )$ Algorithm for the Continuous p-Center Problem on a Tree, Selection and sorting in totally monotone arrays, Multidimensional binary partitions: distributed data structures for spatial partitioning, Maximum likelihood estimation of cell probabilities in constrained multinomial models

Uses Software

Find

Cites Work