Lower Bounds for Selection in X + Y and Other Multisets

Publisher Website
Google Scholar
Abstract
It ~S known that the structure in the muhiset X + Y, for X and Y multlsets of n real numbers, enables selection to be performed more quickly than m other sets of size O(n 2) In this paper a lower bound of f~(max(n, K 1/2 log K)) is given for selecting the Kth element in X + X, and thus in X + Y, for K selecting the first through the median element Selection of gaps, that is, consecutive differences in a sorted order, is shown to be f~(n log n) for all K These results hold also when inputs are restricted to integers The problem of selection on X + X can be generalized to selection on the set of mulusets of size m chosen from X, where the multlsets are ranked on the sums of their elements When m and n grow, selection of the Kth largest muluset of size m is NP- hard when inputs are expressed in binary notation If subsets of Xare characterized as paths, orcmts, or spanning trees of an edge-weighted graph, then selecuon of the Kth largest such subset of X remains NP-hard It is not possible to show these problems to be NP-hard when inputs are expressed m unary, since algorithms exist which run m time polynomml m the sums of the values of the inputs

This publication has 10 references indexed in Scilit: