Donald Bren School of Information and Computer Sciences

Given a set of n real values, each with a positive weight, we wish to find the subset of n —k values having maximum weighted average. This is equivalent to the following form of parametric selection: given n objects with values decreasing linearly with time, find the time at which the n —k maximum values add to zero. We give several algorithms showing that these problems can be solved in time O(n) (independent of k). We also show that a slight generalization of the original problem, in which weights are allowed to be negative, is NP-complete.