File Download
There are no files associated with this item.
Links for fulltext
(May Require Subscription)
 Publisher Website: 10.1007/9783319213989_4
 Find via
Supplementary

Citations:
 Appears in Collections:
Conference Paper: Strategyproof mechanism for obnoxious facility location on a line
Title  Strategyproof mechanism for obnoxious facility location on a line 

Authors  
Issue Date  2015 
Publisher  Springer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/ 
Citation  The 21st Annual International Computing and Combinatorics Conference (COCOON 2015), Beijing, China, 46 August 2015. In Lecture Notes in Computer Science, 2015, v. 9198, p. 4556 How to Cite? 
Abstract  In the problem of obnoxious facility location, an obnoxious facility is located in an area. To maximize the social welfare, e.g., the sum of distances from all the agents to the facility, we have to get the true locations of each agent. However, each agent may misreport his/her location to stay far away from the obnoxious facility. In this paper, we design strategyproof mechanisms on locating an obnoxious facility on a real line. Two objective functions, i.e., maximizing the sum of squares of distances (maxSOS) and maximizing the sum of distances (maxSum), have been considered. For maxSOS, a randomized strategyproof mechanism with approximation ratio 5 / 3 is given, meanwhile the lower bound is proved to be at least 1.042. The lower bound of any randomized strategyproof mechanisms w.r.t. maxSum is proved to be 1.077. Moreover, an extended model that each agent controls multiple locations is considered. For this model, we investigate deterministic and randomized strategyproof mechanisms w.r.t. maxSum and maxSOS objectives, respectively. The deterministic mechanisms are shown to be tight for both objectives. 
Description  LNCS v. 9198 entitled: Computing and Combinatorics: 21st International Conference, COCOON 2015, Beijing, China, August 46, 2015, Proceedings 
Persistent Identifier  http://hdl.handle.net/10722/219224 
ISBN  
ISSN  2005 Impact Factor: 0.402 2015 SCImago Journal Rankings: 0.252 
DC Field  Value  Language 

dc.contributor.author  Ye, D   
dc.contributor.author  Mei, L   
dc.contributor.author  Zhang, Y   
dc.date.accessioned  20150918T07:18:11Z   
dc.date.available  20150918T07:18:11Z   
dc.date.issued  2015   
dc.identifier.citation  The 21st Annual International Computing and Combinatorics Conference (COCOON 2015), Beijing, China, 46 August 2015. In Lecture Notes in Computer Science, 2015, v. 9198, p. 4556   
dc.identifier.isbn  9783319213972   
dc.identifier.issn  03029743   
dc.identifier.uri  http://hdl.handle.net/10722/219224   
dc.description  LNCS v. 9198 entitled: Computing and Combinatorics: 21st International Conference, COCOON 2015, Beijing, China, August 46, 2015, Proceedings   
dc.description.abstract  In the problem of obnoxious facility location, an obnoxious facility is located in an area. To maximize the social welfare, e.g., the sum of distances from all the agents to the facility, we have to get the true locations of each agent. However, each agent may misreport his/her location to stay far away from the obnoxious facility. In this paper, we design strategyproof mechanisms on locating an obnoxious facility on a real line. Two objective functions, i.e., maximizing the sum of squares of distances (maxSOS) and maximizing the sum of distances (maxSum), have been considered. For maxSOS, a randomized strategyproof mechanism with approximation ratio 5 / 3 is given, meanwhile the lower bound is proved to be at least 1.042. The lower bound of any randomized strategyproof mechanisms w.r.t. maxSum is proved to be 1.077. Moreover, an extended model that each agent controls multiple locations is considered. For this model, we investigate deterministic and randomized strategyproof mechanisms w.r.t. maxSum and maxSOS objectives, respectively. The deterministic mechanisms are shown to be tight for both objectives.   
dc.language  eng   
dc.publisher  Springer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/   
dc.relation.ispartof  Lecture Notes in Computer Science   
dc.rights  The final publication is available at Springer via http://dx.doi.org/10.1007/9783319213989_4   
dc.title  Strategyproof mechanism for obnoxious facility location on a line   
dc.type  Conference_Paper   
dc.identifier.email  Zhang, Y: yongzh@hku.hk   
dc.identifier.doi  10.1007/9783319213989_4   
dc.identifier.hkuros  253617   
dc.identifier.volume  9198   
dc.identifier.spage  45   
dc.identifier.epage  56   
dc.publisher.place  Germany   
dc.customcontrol.immutable  sml 151222   