首页 | 本学科首页   官方微博 | 高级检索  
     


Competitive facility location: the Voronoi game
Authors:Hee-Kap Ahn, Siu-Wing Cheng, Otfried Cheong, Mordecai Golin,Ren   van Oostrum
Affiliation:

a Image Media Research Center, Korea Institute of Science & Technology, P.O. Box 131, CheongRyang, Seoul, South Korea

b Department of Computer Science, HKUST, Clear Water Bay, Kowloon, Hong Kong

c Institute of Information & Computing Sciences, Utrecht University, Netherlands

Abstract:We consider a competitive facility location problem with two players. Players alternate placing points, one at a time, into the playing arena, until each of them has placed n points. The arena is then subdivided according to the nearest-neighbor rule, and the player whose points control the larger area wins. We present a winning strategy for the second player, where the arena is a circle or a line segment. We permit variations where players can play more than one point at a time, and show that the first player can ensure that the second player wins by an arbitrarily small margin.
Keywords:Facility location   Game theory
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号