Consecutive Optimizers for a Partitioning Problem with Applications to Optimal Inventory Groupings for Joint Replenishment

A. K. Chakravarty, J. B. Orlin and U. G. Rothblum
Additional contact information
A. K. Chakravarty: University of Wisconsin, Milwaukee, Wisconsin
J. B. Orlin: Massachusetts Institute of Technology, Cambridge, Massachusetts
U. G. Rothblum: Technion, Israel Institute of Technology, Haifa, Israel

Operations Research, 1985, vol. 33, issue 4, 820-834

Abstract: We consider several subclasses of the problem of grouping n items (indexed 1, 2, …, n ) into m subsets so as to minimize the function g ( S 1 , …, S m ). In general, these problems are very difficult to solve to optimality, even for the case m = 2. We provide several sufficient conditions on g (·) that guarantee that there is an optimum partition in which each subset consists of consecutive integers (or else the partition S 1 , …, S m satisfies a more general condition called “semiconsecutiveness”). Moreover, by restricting attention to “consecutive” (or “semiconsecutive”) partitions, we can solve the partition problem in polynomial time for small values of m . If, in addition, g is symmetric, then the partition problem is solvable in purely polynomial time. We apply these results to generalizations of a problem in inventory groupings considered by the authors in a previous paper. We also relate the results to the Neyman-Pearson lemma in statistical hypothesis testing and to a graph partitioning problem of Barnes and Hoffman.

Keywords: 334 partitioning items into subgroups; 625 optimal inventory groupings (search for similar items in EconPapers)
Date: 1985
References: Add references at CitEc
Citations: View citations in EconPapers (10)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.33.4.820 (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:33:y:1985:i:4:p:820-834

Access Statistics for this article

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