Lower Bounds for Selection in X + Y and Other Multisets

DOI10.1145/322092.322097zbMath0388.68057OpenAlexW2053364286MaRDI QIDQ4170251

Samuel D. Kashdan, Donald B. Johnson

Publication date: 1978

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/322092.322097

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Discrete mathematics in relation to computer science (68R99)

Related Items

Simple characterizations of \(P(\# P)\) and complete problems, Bi-immunity separates strong NP-completeness notions, Graph embedding in SYNCHEM2, an expert system for organic synthesis discovery, Complexity of selection in \(X+Y\), Optimal algorithms for generalized searching in sorted matrices, The complexity of the \(K\)th largest subset problem and related problems, The complexity of searching in \(X+Y\) and other multisets, The complexity of selection and ranking in X+Y and matrices with sorted columns, Percentile queries in multi-dimensional Markov decision processes, On the spanning trees of weighted graphs, Meet your expectations with guarantees: beyond worst-case synthesis in quantitative games, On the spanning trees of weighted graphs, Algorithm 616: fast computation of the Hodges-Lehmann location estimator, The computational complexity of the criticality problems in a network with interval activity times, Selection in \(X+Y\) and matrices with sorted rows and columns