The complexity of selection and ranking in X+Y and matrices with sorted columns

DOI10.1016/0022-0000(82)90048-4zbMath0478.68062MaRDI QIDQ1161291

Greg N. Frederickson, Donald B. Johnson

Publication date: 1982

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

Full work available at URL: https://doi.org/10.1016/0022-0000(82)90048-4

Mathematics Subject Classification ID

68P10: Searching and sorting

Related Items

A heuristic for decomposing traffic matrices in TDMA satellite communication, 3-PIERCING OF d-DIMENSIONAL BOXES AND HOMOTHETIC TRIANGLES, A polynomial algorithm for resourse allocation problems with polymatroid constrains¹, An efficient algorithm for the Lagrangean dual of nonlinear knapsack problems with additional nested constraints, An efficient implementation of priority queues using fixed-sized systolic coprocessors, Two algorithms for maximizing a separable concave function over a polymatroid feasible region, An algorithm for the fair resource allocation problem with a submodular constraint, A distributed selection algorithm and its expected communication complexity, On the parallel-decomposability of geometric problems, Finding the closest extreme vertex to a fixed point, On some geometric selection and optimization problems via sorted matrices, Optimal binary trees with order constraints, An optimal parallel algorithm for merging using multiselection, Iterated nearest neighbors and finding minimal polytopes, A short proof of optimality of the bottom up algorithm for discrete resource allocation problems, A nonlinear knapsack problem, Selection and sorting in totally monotone arrays