Skip to main content
eScholarship
Open Access Publications from the University of California

Choosing subsets with maximum weighted average

  • Author(s): Eppstein, David
  • Hirschberg, Daniel S.
  • et al.
Abstract

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.

Main Content
Current View