Selecting the Kth Element in $X + Y$ and $X_1 + X_2 + \cdots + X_m $

DOI10.1137/0207013zbMath0375.68022OpenAlexW2040895999MaRDI QIDQ4154059

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)

Related Items

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