Optimal partitioning which maximizes the sum of the weighted averages

Optimal partitioning which maximizes the sum of the weighted averages

0.00 Avg rating0 Votes
Article ID: iaor19982364
Country: United States
Volume: 43
Issue: 3
Start Page Number: 500
End Page Number: 508
Publication Date: May 1995
Journal: Operations Research
Authors: ,
Keywords: combinatorial analysis
Abstract:

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 pi and a specific weight wi, 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 have an especially simple characterization: There exist two numbers α and &bgr;, with min wi < α < &bgr; ⩽ max wi, such that all the elements with weight wi satisfying α ⩽ wi ⩽ &bgr; 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.

Reviews

Required fields are marked *. Your email address will not be published.