Generalized Selection and Ranking: Sorted Matrices

DOI10.1137/0213002zbMATH Open0537.68059OpenAlexW2004899468MaRDI QIDQ3323282FDOQ3323282

Authors: Greg N. Frederickson, Donald B. Johnson 

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

Recommendations

• Optimal parallel selection in sorted matrices
• Selection in \(X+Y\) and matrices with sorted rows and columns
• Selection in Monotone Matrices and Computingkth Nearest Neighbors
• On parallel selection and searching in partial orders: Sorted matrices
• scientific article; zbMATH DE number 742987

zbMATH Keywords

selectionalgorithmrankingdata structureslower boundssorted matricescartesian sumssuccinct descriptions

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10)

Cited In (65)

• Title not available (Why is that?)
• Faster distance-based representative skyline and \(k\)-center along Pareto front in the plane
• Selection from heaps, row-sorted matrices, and \(X+Y\) using soft heaps
• Geometric applications of posets
• Minkowski sum selection and finding
• Improved algorithms for the bichromatic two-center problem for pairs of points
• River routing in VLSI
• Optimal algorithms for generalized searching in sorted matrices
• The centdian subtree on tree networks
• Fast algorithms for the maximum convolution problem
• Improved algorithms for the continuous tree edge-partition problems and a note on ratio and sorted matrices searches
• Fitting a step function to a point set
• Computing fair and bottleneck matchings in geometric graphs
• Selection in monotone matrices and computing k th nearest neighbors
• Optimizing squares covering a set of points
• A randomized algorithm for weighted approximation of points by a step function
• Title not available (Why is that?)
• Cache-oblivious selection in sorted \(X+Y\) matrices
• Computing the maximum overlap of two convex polygons under translations
• Efficiently approximating color-spanning balls
• Approximating points by a piecewise linear function
• Computing a minimum-width square or rectangular annulus with outliers
• Geometric applications of posets
• Constrained square-center problems
• On parsimonious explanations for 2-D tree- and linearly-ordered data
• An \(\Omega (n\log n)\) lower bound for computing the sum of even-ranked elements
• Optimal location with equitable loads
• 3-PIERCING OF d-DIMENSIONAL BOXES AND HOMOTHETIC TRIANGLES
• Linear-time algorithms for proportional apportionment
• Enclosing \(k\) points in the smallest axis parallel rectangle
• Labeling a rectilinear map more efficiently
• Region-restricted clustering for geographic data mining
• THE ALIGNED K-CENTER PROBLEM
• Finding axis-parallel rectangles of fixed perimeter or area containing the largest number of points
• On \(r\)-gatherings on the line
• A simple algorithm for \(r\)-gatherings on the line
• Ranking \(k\) maximum sums
• Reverse shortest path problem in weighted unit-disk graphs
• Linear-time fitting of a \(k\)-step function
• Linear-time fitting of a \(k\)-step function
• CONSTRUCTING OPTIMAL HIGHWAYS
• On some geometric selection and optimization problems via sorted matrices
• Matching sets of line segments
• A simple linear algorithm for computing rectilinear 3-centers
• Fitting a Step Function to a Point Set
• An \(O(n\log n)\)-time algorithm for the \(k\)-center problem in trees
• Selection in \(X+Y\) and matrices with sorted rows and columns
• Improved algorithms for placing undesirable facilities
• Facility location problems with uncertainty on the plane
• Computing the discrete Fréchet distance with imprecise input
• Covering a point set by two disjoint rectangles
• Scheduling with gaps: new models and algorithms
• The complexity of searching in \(X+Y\) and other multisets
• Jaywalking your dog: computing the Fréchet distance with shortcuts
• Weighted \(L_{\infty}\) isotonic regression
• An \(O(n\log n)\)-time algorithm for the \(k\)-center problem in trees
• Obnoxious facility location: complete service with minimal harm
• Stacks, queues, and deques with order-statistic operations
• Storing matrices on disk for efficient row and column retrieval
• On some geometric selection and optimization problems via sorted matrices
• Light graphs with small routing cost
• Optimal parallel selection in sorted matrices
• Approximation algorithms for orthogonal line centers
• The Euclidean bottleneck Steiner path problem and other applications of \((\alpha ,\beta )\)-pair decomposition
• Near-linear approximation algorithms for geometric hitting sets

This page was built for publication: Generalized Selection and Ranking: Sorted Matrices

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3323282)