In this paper,we investigate the obnoxious facility location game with weighted agents.First,we design a randomized group strategy-proof mechanism with approximation ratio 3Wmax 2Wmin when the weighted agents are loca...In this paper,we investigate the obnoxious facility location game with weighted agents.First,we design a randomized group strategy-proof mechanism with approximation ratio 3Wmax 2Wmin when the weighted agents are located on a line;then,on the cycle metric,we also discuss the strategy-proofness and the approximation ratios of a class of group strategy-proof deterministic mechanisms.展开更多
This paper deals with the pos/neg-weighted p-median problem on tree graphs where all customers are modeled as subtrees. We present a polynomial algorithm for the 2-median problem on an arbitrary tree. Then we improve ...This paper deals with the pos/neg-weighted p-median problem on tree graphs where all customers are modeled as subtrees. We present a polynomial algorithm for the 2-median problem on an arbitrary tree. Then we improve the time complexity to O（n logn） for the problem on a balanced tree, where n is the number of the vertices in the tree.展开更多
基金the National Natural Science Foundation of China(No.61365013)the Natural Science Foundation of Jiangxi Province(Nos.20142BAB211020 and 20142BAB211004).
文摘In this paper,we investigate the obnoxious facility location game with weighted agents.First,we design a randomized group strategy-proof mechanism with approximation ratio 3Wmax 2Wmin when the weighted agents are located on a line;then,on the cycle metric,we also discuss the strategy-proofness and the approximation ratios of a class of group strategy-proof deterministic mechanisms.
基金Supported by the National Nature Science Foundation of China(Nos.11471210,11571222)
文摘This paper deals with the pos/neg-weighted p-median problem on tree graphs where all customers are modeled as subtrees. We present a polynomial algorithm for the 2-median problem on an arbitrary tree. Then we improve the time complexity to O（n logn） for the problem on a balanced tree, where n is the number of the vertices in the tree.
