Optimal Partitioning Which Maximizes the Sum of the Weighted Averages

Shmuel Gal and Boris Klots
Additional contact information
Shmuel Gal: IBM Israel Science and Technology Ltd., Haifa, Israel
Boris Klots: IBM Israel Science and Technology Ltd., Haifa, Israel

Operations Research, 1995, vol. 43, issue 3, 500-508

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 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 α and β, with min w i w i , such that all the elements with weight w i satisfying α ≤ w i ≤ β 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.

Keywords: analysis of algorithms; computational complexity; polynormal algorithms; computers; systems design; partitioning of program items; mathematics; combinatorics; optimal partitioning (search for similar items in EconPapers)
Date: 1995
References: Add references at CitEc
Citations: View citations in EconPapers (6)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.43.3.500 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:43:y:1995:i:3:p:500-508

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().