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.展开更多
In this paper,we investigate the problem of minimizing the ratio of normalized non-negative monotone non-submodular set function f and normalized non-negative monotone set function g.We take advantage of the greedy te...In this paper,we investigate the problem of minimizing the ratio of normalized non-negative monotone non-submodular set function f and normalized non-negative monotone set function g.We take advantage of the greedy technique and get a per-formance guarantee depending on the generalized curvature and inverse generalized curvature of f,as well as the submodularity ratio of g.Our results generalize the works of Bai et al.(Algorithms for optimizing the ratio of submodular functions.In:Proceedings of the 33rd International Conference on Machine L earning,2016)and Qian et al.(Optimizing ratio of monotone set functions.In:Proceedings of the 26th International Joint Conference on Artificial Intelligence,2017).展开更多
基金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.
基金Da-Chuan Xu’s research was supported by the National Natural Science Foundation of China(No.11531014)Yan-Jun Jiang was supported by the National Natural Science Foundation of China(No.11801251)Dong-Mei Zhang was supported by the National Natural Science Foundation of China(No.11871081).
文摘In this paper,we investigate the problem of minimizing the ratio of normalized non-negative monotone non-submodular set function f and normalized non-negative monotone set function g.We take advantage of the greedy technique and get a per-formance guarantee depending on the generalized curvature and inverse generalized curvature of f,as well as the submodularity ratio of g.Our results generalize the works of Bai et al.(Algorithms for optimizing the ratio of submodular functions.In:Proceedings of the 33rd International Conference on Machine L earning,2016)and Qian et al.(Optimizing ratio of monotone set functions.In:Proceedings of the 26th International Joint Conference on Artificial Intelligence,2017).
