Selecting the Kth Element in X + Y and X₁ + X₂ + \cdots + X_m

DOI10.1137/0207013MaRDI QIDQ4154059zbMATHOpenAlexFDO

Authors Donald B. Johnson, Tetsuo Mizoguchi

Publication date 1978

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/0207013

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Algorithms in computer science (68W99)

Cited in

(32)

• On search over rationals
• eummd
• A routing and scheduling approach to rail transportation of hazardous materials with demand due dates
• Weighted selectin for the multiset x∓xwith application to r–estimates and associated confidence limits
• Online analysis of time series by the \(Q_n\) estimator
• Selection in \(X+Y\) and matrices with sorted rows and columns
• Simple characterizations of \(P(\# P)\) and complete problems
• Algorithm 1034: an accelerated algorithm to compute the \(Q_n\) robust statistic, with corrections to constants
• The complexity of searching in \(X+Y\) and other multisets
• The complexity of the \(K\)th largest subset problem and related problems
• Weighted median algorithms for \(L_ 1\) approximation
• Algorithm 616: fast computation of the Hodges-Lehmann location estimator
• The Kantorovich metric for probability measures on the circle
• A simple and competitive estimator of location
• A robust scale estimator based on pairwise means
• Generating the best \(K\) sequences in relocation problems
• An O(n) algorithm for the linear multiple choice knapsack problem and related problems
• A linear-time algorithm for solving continuous maximin knapsack problems
• Efficient calculation of hodges-lehmann estimators of location
• Solving a class of multiplicative programs with 0-1 knapsack constraints
• A linear time algorithm for a matching problem on the circle
• An $O ( ( n\log p )^2 )$ Algorithm for the Continuous p-Center Problem on a Tree
• EuMMD: efficiently computing the MMD two-sample test statistic for univariate data
• Incomplete generalized \(L\)-statistics
• A faster polynomial algorithm for the unbalanced Hitchcock transportation problem
• Selection in monotone matrices and computing k th nearest neighbors
• Complexity of selection in \(X+Y\)
• A parallel selection algorithm
• The complexity of selection and ranking in X+Y and matrices with sorted columns
• The stochastic linear continuous type knapsack problem: A generalized P model
• Optimal algorithms for generalized searching in sorted matrices
• AnO (n)-algorithm for LP-knapsacks with a fixed number of GUB constraints

This page was built for publication: Selecting the Kth Element in $X + Y$ and $X_1 + X_2 + \cdots + X_m $

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