Article Contents
Article Contents

# The warehouse-retailer network design game

• In this paper, we consider the warehouse-retailer network design game based on the warehouse-retailer network design problem (WRND) proposed by Teo and Shu (2004). By carefully defining the generalized distance function, we present a cost-sharing method for the warehouse-retailer network design game. We show that the proposed cost-sharing scheme is cross-monotonic, competitive, and $3$-approximate cost recovery.
Mathematics Subject Classification: Primary: 90C59; Secondary: 90C10.

 Citation:

•  [1] N. R. Devanur, M. Mihail and V. V. Vazirani, Strategyproof cost-sharing mechanisms for set cover and facility location games, Proceedings of the 4th ACM conference on Electronic commerce, (2003), 108-114.doi: 10.1145/779928.779942. [2] L. Fleischer and S. Iwata, A push-relabel framework for submodular function minimization and applications to parametric optimization, Discrete Applied Mathematics, 131 (2003), 311-322.doi: 10.1016/S0166-218X(02)00458-4. [3] M. X. Goemans and M. Skutella, Cooperative facility location games, Journal of Algorithms, 50 (2004), 194-214.doi: 10.1016/S0196-6774(03)00098-1. [4] M. Grötschel, L. Lovász and A. Schrijver, Geometric Algorithms and Combinatorial Optimization, Springer-Verlag, Berlin, 1988.doi: 10.1007/978-3-642-97881-4. [5] N. Immorlica, M. Mahdian and V. Mirrokni, Limitations of cross-monotonic cost-sharing schemes, Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, (2005), 602-611. [6] S. Iwata, L. Fleischer and S. Fujishige, A combinatorial strongly polynomial algorithm for minimizing submodular functions, Journal of the ACM, 48 (2001), 761-777.doi: 10.1145/502090.502096. [7] K. Jain and V. V. Vazirani, Applications of approximation algorithms to cooperative games, Proceedings of the Thirty-Third Annual ACM Symposium on Theory of Computing, (2001), 364-372.doi: 10.1145/380752.380825. [8] G. Li, Y. Li, J. Shu and D. Xu, A cross-monotonic cost-sharing scheme for the concave facility location game, Journal of Global Optimization, 56 (2013), 1325-1334.doi: 10.1007/s10898-012-9852-0. [9] Y. Li, J. Shu, X. Wang, N. Xiu, D. Xu and J. Zhang, Approximation algorithms for integrated distribution network design problem, INFORMS Journal on Computing, 25 (2013), 572-584.doi: 10.1287/ijoc.1120.0522. [10] W. Lim, J. Ou and C. Teo, Inventory cost effect of consolidating several one-warehouse multiretailer systems, Operations Research, 51 (2003), 668-672.doi: 10.1287/opre.51.4.668.16092. [11] H. Moulin and S. Shenker, Strategyproof sharing of submodular costs: Budget balance versus efficiency, Econom Theory, 18 (2001), 511-533.doi: 10.1007/PL00004200. [12] M. Pál and É. Tardos, Group strategyproof mechanisms via primal-dual algorithms, Proceedings of FOCS, (2003), 584-593. [13] R. Roundy, $98%$ Effective integer-ratio lot-sizing for one warehouse multi-retailer systems, Management science, 31 (1985), 1416-1430.doi: 10.1287/mnsc.31.11.1416. [14] A. Schrijver, A combinatorial algorithm minimizing submodular functions in strongly polynomial time, Journal of Combinatorial Theory, Series B, 80 (2000), 346-355.doi: 10.1006/jctb.2000.1989. [15] J. Shu, An efficient greedy heuristic for warehouse-retailer network design optimization, Transportation Science, 44 (2010), 183-192.doi: 10.1287/trsc.1090.0302. [16] J. Shu, C. Teo and Z. Shen, Stochastic transportation-inventory network design problem, Operations Research, 53 (2005), 48-60.doi: 10.1287/opre.1040.0140. [17] C. Teo and J. Shu, Warehouse-retailer network design problem, Operations Research, 52 (2004), 396-408.doi: 10.1287/opre.1030.0096. [18] D. Xu and D. Du, The $k$-level facility location game, Operation Research Letter, 34 (2006), 421-426.doi: 10.1016/j.orl.2005.06.002. [19] J. Zhang, Cost allocation for joint replenishment models, Operations Research, 57 (2009), 146-156.doi: 10.1287/opre.1070.0491.