Generalized Selection and Ranking: Sorted Matrices
From MaRDI portal
Publication:3323282
DOI10.1137/0213002zbMath0537.68059OpenAlexW2004899468MaRDI QIDQ3323282
Donald B. Johnson, Greg N. Frederickson
Publication date: 1984
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0213002
algorithmrankingselectiondata structureslower boundssorted matricescartesian sumssuccinct descriptions
Related Items
Improved algorithms for the bichromatic two-center problem for pairs of points, Fast algorithms for the maximum convolution problem, Efficiently approximating color-spanning balls, Computing a minimum-width square or rectangular annulus with outliers, Approximation algorithms for orthogonal line centers, Enclosing \(k\) points in the smallest axis parallel rectangle, Labeling a rectilinear map more efficiently, Light graphs with small routing cost, Approximating points by a piecewise linear function, On r-Gatherings on the Line, Constrained square-center problems, A RANDOMIZED ALGORITHM FOR WEIGHTED APPROXIMATION OF POINTS BY A STEP FUNCTION, Selection in monotone matrices and computing k th nearest neighbors, River routing in VLSI, Reverse shortest path problem in weighted unit-disk graphs, Matching sets of line segments, Weighted \(L_{\infty}\) isotonic regression, Linear-Time Algorithms for Proportional Apportionment, Linear-time fitting of a \(k\)-step function, Ranking \(k\) maximum sums, Optimal algorithms for generalized searching in sorted matrices, Geometric Applications of Posets, Dispersing facilities on planar segment and circle amidst repulsion, Improved algorithms for placing undesirable facilities, Faster distance-based representative skyline and \(k\)-center along Pareto front in the plane, Near-linear approximation algorithms for geometric hitting sets, The complexity of searching in \(X+Y\) and other multisets, The Euclidean bottleneck Steiner path problem and other applications of \((\alpha ,\beta )\)-pair decomposition, OBNOXIOUS FACILITY LOCATION: COMPLETE SERVICE WITH MINIMAL HARM, Fitting a Step Function to a Point Set, THE ALIGNED K-CENTER PROBLEM, Optimal parallel selection in sorted matrices, Optimizing squares covering a set of points, COMPUTING THE DISCRETE FRÉCHET DISTANCE WITH IMPRECISE INPUT, Stacks, queues, and deques with order-statistic operations, A simple linear algorithm for computing rectilinear 3-centers, Fitting a step function to a point set, Improved algorithms for the continuous tree edge-partition problems and a note on ratio and sorted matrices searches, Cache-oblivious selection in sorted \(X+Y\) matrices, Facility location problems with uncertainty on the plane, An improved algorithm for diameter-optimally augmenting paths in a metric space, On some geometric selection and optimization problems via sorted matrices, Algorithms for covering multiple barriers, 3-PIERCING OF d-DIMENSIONAL BOXES AND HOMOTHETIC TRIANGLES, Linear-Time Fitting of a k-Step Function, Region-restricted clustering for geographic data mining, CONSTRUCTING OPTIMAL HIGHWAYS, Unnamed Item, On some geometric selection and optimization problems via sorted matrices, MINKOWSKI SUM SELECTION AND FINDING, COVERING A POINT SET BY TWO DISJOINT RECTANGLES, Scheduling with gaps: new models and algorithms, Optimal location with equitable loads, Selection in \(X+Y\) and matrices with sorted rows and columns, Geometric applications of posets, A Simple Algorithm for $r$-gatherings on the Line, Finding axis-parallel rectangles of fixed perimeter or area containing the largest number of points, An O(n log n)-Time Algorithm for the k-Center Problem in Trees, An $O(n\log n)$-Time Algorithm for the $k$-Center Problem in Trees, Unnamed Item, The centdian subtree on tree networks
