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

DOI10.1016/0022-0000(82)90048-4zbMath0478.68062OpenAlexW2019315437MaRDI 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

Searching and sorting (68P10)

Related Items

Iterated nearest neighbors and finding minimal polytopes, Improved algorithms for the bichromatic two-center problem for pairs of points, Dynamic layers of maxima with applications to dominating queries, Exact methods for the knapsack problem and its generalizations, Kinetic \(k\)-semi-Yao graph and its applications, Algorithms for separable convex optimization with linear ascending constraints, Covering a set of points by two axis-parallel boxes, Finding the k shortest paths in parallel, Space-efficient indexes for forbidden extension queries, Improved algorithms for some competitive location centroid problems on paths, trees and graphs, Selection and sorting in totally monotone arrays, A heuristic for decomposing traffic matrices in TDMA satellite communication, A nonlinear knapsack problem, Distributed algorithms for selection in sets, L-infinity interdistance selection by parametric search, Fast integer-valued algorithms for optimal allocations under constraints in stratified sampling, A short proof of optimality of the bottom up algorithm for discrete resource allocation problems, A New Combinatorial Algorithm for Separable Convex Resource Allocation with Nested Bound Constraints, Matching sets of line segments, On a Reduction for a Class of Resource Allocation Problems, Efficient Algorithms for Optimization and Selection on Series-Parallel Graphs, Linear-Time Algorithms for Proportional Apportionment, Optimal eviction policies for stochastic address traces, Ranking \(k\) maximum sums, Algorithms for the item assortment problem: an application to vending machine products, Geometric p-Center Problems with Centers Constrained to Two Lines, Range queries on uncertain data, Faster distance-based representative skyline and \(k\)-center along Pareto front in the plane, Improved algorithms for several network location problems with equality measures., Representing a functional curve by curves with fewer peaks, Polymatroidal flow network models with multiple sinks, A polynomial algorithm for resourse allocation problems with polymatroid constrains¹, A Sub-cubic Time Algorithm for the k-Maximum Subarray Problem, 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, An efficient algorithm for the Lagrangean dual of nonlinear knapsack problems with additional nested constraints, A distributed selection algorithm and its expected communication complexity, On the parallel-decomposability of geometric problems, Optimizing squares covering a set of points, Algorithms for finding the weight-constrained \(k\) longest paths in a tree and the length-constrained \(k\) maximum-sum segments of a sequence, Necklaces, convolutions, and \(X+Y\), An efficient implementation of priority queues using fixed-sized systolic coprocessors, Finding the closest extreme vertex to a fixed point, Complexity and algorithms for nonlinear optimization problems, The algebraic Monge property and path problems, Improved algorithms for the continuous tree edge-partition problems and a note on ratio and sorted matrices searches, ON ENUMERATING AND SELECTING DISTANCES, An algorithm for a separable integer programming problem with cumulatively bounded variables, On some geometric selection and optimization problems via sorted matrices, Geometric pattern matching for point sets in the plane under similarity transformations, On an optimization problem with nested constraints, 3-PIERCING OF d-DIMENSIONAL BOXES AND HOMOTHETIC TRIANGLES, Unnamed Item, A Decomposition Algorithm for Nested Resource Allocation Problems, On some geometric selection and optimization problems via sorted matrices, Scheduling with gaps: new models and algorithms, Dynamic ham-sandwich cuts in the plane, Selection in \(X+Y\) and matrices with sorted rows and columns, Optimal binary trees with order constraints, Finding axis-parallel rectangles of fixed perimeter or area containing the largest number of points, One-way and round-trip center location problems, An efficient algorithm for the parametric resource allocation problem, A fast algorithm for the linear multiple-choice knapsack problem, Locating two obnoxious facilities using the weighted maximin criterion, Dominance Product and High-Dimensional Closest Pair under L_infty, On constant factors in comparison-based geometric algorithms and data structures, An optimal parallel algorithm for merging using multiselection, The discrete forward-reserve problem -- allocating space, selecting products, and area sizing in forward order picking

Cites Work