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 install...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.展开更多
This paper considers a variant of the classical facility location game called the uncapacitared facility location game with penalties （UFLGWP）. Unlike the standard UFLG, each client in the UFLGWP is either assigned ...This paper considers a variant of the classical facility location game called the uncapacitared facility location game with penalties （UFLGWP）. Unlike the standard UFLG, each client in the UFLGWP is either assigned to an open facility or rejected by paying a penalty. The authors propose a 3-approximate cross-monotonic cost-sharing method for the UFLGWP.展开更多
We study the soft-capacitated facility location game which is an extension of the facility location game of Pa1 and Tardos. We propose a 6-approximate cross-monotonic cost-sharing method. Numerical tests indicate that...We study the soft-capacitated facility location game which is an extension of the facility location game of Pa1 and Tardos. We propose a 6-approximate cross-monotonic cost-sharing method. Numerical tests indicate that the method is effective.展开更多
In the k-level facility location problem with penalties,each client will be either serviced or rejected completely.And if the client is planned to be serviced,then it must be connected to a sequence of k different kin...In the k-level facility location problem with penalties,each client will be either serviced or rejected completely.And if the client is planned to be serviced,then it must be connected to a sequence of k different kinds of facilities located in k levels of hierarchy.The total cost including the facility cost,connection cost and penalty cost will be jointly paid by all the clients.In the corresponding game of the k-level facility location problem with penalties,called the k-level facility location game with penalties,the total cost should be allocated to different clients.This work set out a cost-sharing scheme for the k-level facility location game with penalties that is cross-monotonic,competitive,and the approximate cost recovery is 6.展开更多
基金supported by National Natural Science Foundation of China (Grant Nos. 60773185, 10401038)Program for Beijing Excellent Talents (Grant No. 20071D050150020S)
文摘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.
基金supported by the National Natural Science Foundation of China under Grant Nos.60773185 and 11071268Program for Beijing Excellent Talents
文摘This paper considers a variant of the classical facility location game called the uncapacitared facility location game with penalties （UFLGWP）. Unlike the standard UFLG, each client in the UFLGWP is either assigned to an open facility or rejected by paying a penalty. The authors propose a 3-approximate cross-monotonic cost-sharing method for the UFLGWP.
基金Supported by the National Natural Science Foundation of China(No.60773185,10401038) and Program for Beijing Excellent Talents
文摘We study the soft-capacitated facility location game which is an extension of the facility location game of Pa1 and Tardos. We propose a 6-approximate cross-monotonic cost-sharing method. Numerical tests indicate that the method is effective.
基金This research was supported by the National Natural Science Foundation of China(Nos.11901544 and 11801251).
文摘In the k-level facility location problem with penalties,each client will be either serviced or rejected completely.And if the client is planned to be serviced,then it must be connected to a sequence of k different kinds of facilities located in k levels of hierarchy.The total cost including the facility cost,connection cost and penalty cost will be jointly paid by all the clients.In the corresponding game of the k-level facility location problem with penalties,called the k-level facility location game with penalties,the total cost should be allocated to different clients.This work set out a cost-sharing scheme for the k-level facility location game with penalties that is cross-monotonic,competitive,and the approximate cost recovery is 6.
