OPTIMAL PARTITIONING WHICH MAXIMIZES THE SUM OF THE WEIGHTED AVERAGES
成果类型：
Article
署名作者：
GAL, S; KLOTS, B
刊物名称：
OPERATIONS RESEARCH
ISSN/ISSBN：
0030-364X
DOI：
10.1287/opre.43.3.500
发表日期：
1995
页码：
500-508
关键词：
摘要：
We consider an optimal partitioning problem that occurs in the assignment of computer jobs to a multiple cache and in other combinatorial optimization problems: For a given set of n elements, where each element i has a given frequency p(i) and a specific weight w(i), we would like to divide the elements into m mutually exclusive groups such that the sum over all the groups of the average group weight is maximal. We characterize the optimal solution and present an algorithm which is polynomial in n for obtaining the optimal partitioning. Optimal partitioning policies for two groups has an especially simple characterization: There exist two numbers alpha and beta, with min w(i) < alpha < beta less-than-or-equal-to max w(i), such that all the elements with weight w(i) satisfying alpha less-than-or-equal-to w(i) less-than-or-equal-to beta belong to one group and all other elements belong to the other group. A modification of this policy gives the optimal partitioning for an arbitrary number of groups.