CHOOSING SUBSETS WITH MAXIMUM WEIGHTED AVERAGE

Authors
EPPSTEIN D HIRSCHBERG DS
Citation
D. Eppstein et Ds. Hirschberg, CHOOSING SUBSETS WITH MAXIMUM WEIGHTED AVERAGE, Journal of algorithms, 24(1), 1997, pp. 177-193
Citations number
24
Categorie Soggetti
Mathematics,Mathematics,"Computer Science Theory & Methods
Journal title
Journal of algorithms → ACNP
ISSN journal
01966774
Volume
24
Issue
1
Year of publication
1997
Pages
177 - 193
Database
ISI
SICI code
0196-6774(1997)24:1<177:CSWMWA>2.0.ZU;2-1
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 o bjects with values decreasing linearly with time, find the time at whi ch the n - k maximum values add to zero. We show that these problems c an be solved in time O(n) (independent of k). A generalization in whic h weights are allowed to be negative is NP-complete. (C) 1997 Academic Press.