×

A cross-monotonic cost sharing method for the facility location game with service installation costs. (English) Zbl 1180.90280

Summary: In this paper, we consider the metric uncapacitated facility location game with service installation costs. Our main result is an 11-approximate cross-monotonic cost-sharing method under the assumption that the installation cost depends only on the service type.

MSC:

91B32 Resource and cost allocation (including fair division, apportionment, etc.)
90B80 Discrete location and assignment
90C27 Combinatorial optimization
91A12 Cooperative games
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Shmoys D, Tardos É, Aardal K. Approximation algorithms for facility location problems (extended abstract). In: Proceedings of the 29th ACM Symposium on Theory of Computing (STOC). New York: ACM, 1997, 265–274 · Zbl 0962.68008
[2] Byrka J, Aardal K. An optimal bifactor approximation algorithm for the metric uncapacitated facility location problem. SIAM J Comput, to appear (2009) · Zbl 1205.90173
[3] Chudak F, Shmoys D. Improved approxiamtion algorithms for the uncapaciteted facility location problem. SIAM J Comput, 33(1): 1–25 (2003) · Zbl 1044.90056 · doi:10.1137/S0097539703405754
[4] Guha S, Khuller S. Greedy strike back: Improved facility location algorithms. J Algorithms, 31: 228–248 (1999) · Zbl 0928.68137 · doi:10.1006/jagm.1998.0993
[5] Jain K, Mahdian M, Saberi A. A new greedy approach for facility location problems. In: Proceedings of the 34th ACM Symposium on Theory of Computing (STOC). New York: ACM, 2002, 731–740 · Zbl 1192.90106
[6] Jain K, Vazirani V V. Approximation algorithms for metric facility location and k-median problems using the primal-dual schema and Lagrangian relaxation. J ACM, 48: 274–296 (2001) · Zbl 1138.90417 · doi:10.1145/375827.375845
[7] Mahdian M, Ye Y, Zhang J. Approximation algorithms for metric facility location problems. SIAM J Comput, 36(2): 411–432 (2006) · Zbl 1151.90590 · doi:10.1137/S0097539703435716
[8] Sviridenko M. An improved approximation algorithm for the metric uncapacitated facility location problem. In: Proceedings of the 9th Integer Programming and Combinatorial Optimization (IPCO). Berlin-Heidelberg: Springer, 2002, 240–257 · Zbl 1049.90520
[9] Aardal K, Chudak F, Shmoys D. A 3-approximation algorithm for the k-level uncapacitated facility location problem. Inform Process Lett, 72: 161–167 (1999) · Zbl 0994.90090 · doi:10.1016/S0020-0190(99)00144-1
[10] Ageev A, Ye Y, Zhang J. Improved combinatorial apporximation algorithms for the k-level facility location problem. SIAM J Discrete Math, 18(1): 207–217 (2004) · Zbl 1087.90037 · doi:10.1137/S0895480102417215
[11] Du D, Wang X, Xu D. An approximation algorithm for the k-level capacitated facility location problem. J Comb Optim, DOI: 10.1007/s10878-009-9213-1 · Zbl 1206.90072
[12] Shmoys D, Swamy C, Levi R. Facility location with service installation costs. In: Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Philadelphia: SIAM, 2004, 1088–1097 · Zbl 1318.90044
[13] Xu D, Du D. The k-level facility location game. Oper Res Lett, 34(4): 421–426 (2006) · Zbl 1133.90365 · doi:10.1016/j.orl.2005.06.002
[14] Xu D, Yang R. A cost-sharing method for an economic lot-sizing game. Oper Res Lett, 37: 107–110 (2009) · Zbl 1159.91333 · doi:10.1016/j.orl.2008.11.001
[15] Zhang J. Approximating the two-level facility location problem via a quasi-greedy approach. Math Program Ser A, 108(1): 159–176 (2006) · Zbl 1142.90440 · doi:10.1007/s10107-006-0704-x
[16] Zhang J, Chen B, Ye Y. A multiexchange local search algorithm for the capacitated facility location problem. Math Oper Res, 30(2): 389–403 (2005) · Zbl 1082.90057 · doi:10.1287/moor.1040.0125
[17] Zhang J, Ye Y. A note on the maximization version of the multi-level facility location problem. Oper Res Lett, 30(5): 333–335 (2002) · Zbl 1010.90037 · doi:10.1016/S0167-6377(02)00183-9
[18] Xu D, Zhang S. Approximation algorithm for facility location with service installation costs. Oper Res Lett, 6: 46–50 (2008) · Zbl 1138.90040 · doi:10.1016/j.orl.2007.04.002
[19] Moulin H, Shenker S. Strategyproof sharing of submodular costs: budget balance versus efficiency. Econom Theory, 18: 511–533 (2001) · Zbl 1087.91509 · doi:10.1007/PL00004200
[20] Pál M, Tardos É. Group strategyproof mechanisms via primal-dual algorithms. In: Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science (FOCS). Washington: IEEE 2003, 584–593
[21] Immorlica N, Mahdian M, Mirrokni V S. Limitations of cross-monotonic cost sharing schemes. In: Proceedings of the 16th Annual ACM-SIAM symposium on Discrete algorithms (SODA). New York: ACM, 2005, 602–611 · Zbl 1297.91016
[22] Goemans M X, Skutella M. Cooperative facility location games. J Algorithms, 50: 194–214 (2004) · Zbl 1106.91009 · doi:10.1016/S0196-6774(03)00098-1
[23] Mallozzi L. Noncooperative facility location games. Oper Res Lett, 35(2): 151–154 (2007) · Zbl 1303.91023 · doi:10.1016/j.orl.2006.03.003
[24] Leonardi S, Schäfer G. Cross-monotonic cost sharing methods for connected facility location games. Theoret Comput Sci, 326: 431–442 (2004) · Zbl 1071.90023 · doi:10.1016/j.tcs.2004.07.033
[25] Li Y, Xu D. Soft-capacitated facility location game. Acta Math Appl Sin Engl Ser, DOI: 10.1007/S10255-008-8111-0 · Zbl 1184.90142
[26] Devanur N R, Mihail M, Vazirani V V. Strategyproof cost-sharing mechanisms for set cover and facility location games. Decis Supp Syst, 39: 11–22 (2005) · doi:10.1016/j.dss.2004.08.004
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.