Polymatroid Optimization, Submodularity, and Joint Replenishment Games

Simai He (), Jiawei Zhang () and Shuzhong Zhang ()
Additional contact information
Simai He: Department of Management Sciences, City University of Hong Kong, Kowloon Tong, Hong Kong
Jiawei Zhang: Department of Information, Operations, and Management Sciences, Stern School of Business, New York University, New York, New York 10012
Shuzhong Zhang: Industrial and Systems Engineering Program, University of Minnesota, Minneapolis, Minnesota 55455

Operations Research, 2012, vol. 60, issue 1, 128-137

Abstract: In this paper we consider the problem of maximizing a separable concave function over a polymatroid. More specifically, we study the submodularity of its optimal objective value in the parameters of the objective function. This question is interesting in its own right and is encountered in many applications. But our research has been motivated mainly by a cooperative game associated with the well-known joint replenishment model. By applying our general results on polymatroid optimization, we prove that this cooperative game is submodular (i.e., its characteristic cost function is submodular) if the joint setup cost is a normalized and nondecreasing submodular function. Furthermore, the same result holds true for a more general one-warehouse multiple retailer game, which affirmatively answers an open question posed by Anily and Haviv [Anily, S., M. Haviv. 2007. The cost allocation problem for the first order interaction joint replenishment model. Oper. Res. 55 (2) 292--302].

Keywords: polymatroid optimization; separable concave function; cooperative games; joint replenishment problem (search for similar items in EconPapers)
Date: 2012
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (6)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.1110.1000 (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:60:y:2012:i:1:p:128-137

Access Statistics for this article

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