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

DOI10.1137/0207013zbMath0375.68022MaRDI 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

68Q25: Analysis of algorithms and problem complexity

68W99: Algorithms in computer science

Related Items

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, The stochastic linear continuous type knapsack problem: A generalized P model, The complexity of searching in \(X+Y\) and other multisets, Weighted median algorithms for \(L_ 1\) approximation, Complexity of selection in \(X+Y\), A linear time algorithm for a matching problem on the circle, The complexity of selection and ranking in X+Y and matrices with sorted columns, On search over rationals, Generating the best \(K\) sequences in relocation problems, A simple and competitive estimator of location, Simple characterizations of \(P(\# P)\) and complete problems, Incomplete generalized \(L\)-statistics, Optimal algorithms for generalized searching in sorted matrices, The Kantorovich metric for probability measures on the circle, Solving a class of multiplicative programs with 0-1 knapsack constraints, A linear-time algorithm for solving continuous maximin knapsack problems, AnO (n)-algorithm for LP-knapsacks with a fixed number of GUB constraints, 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, Efficient calculation of hodges-lehmann estimators of location, An $O ( ( n\log p )^2 )$ Algorithm for the Continuous p-Center Problem on a Tree