On the complexity of the (r|p)-centroid problem in the plane
-
Ivan Davydov [1] ; Yury Kochetov [1] ; Alexandr Plyasunov [1]
-
[1] Novosibirsk State University
Novosibirsk State University
Rusia
-
- Localización: Top, ISSN-e 1863-8279, ISSN 1134-5764, Vol. 22, Nº. 2, 2014, págs. 614-623
- Idioma: inglés
- Enlaces
-
Resumen
In the (r∣p)-centroid problem, two players, called leader and follower, open facilities to service clients. We assume that clients are identified with their location on the Euclidean plane, and facilities can be opened anywhere in the plane. The leader opens p facilities. Later on, the follower opens r facilities. Each client patronizes the closest facility. In case of ties, the leader’s facility is preferred. The goal is to find p facilities for the leader to maximize his market share. We show that this Stackelberg game is ΣP2 -hard. Moreover, we strengthen the previous results for the discrete case and networks. We show that the game is ΣP2 -hard even for planar graphs for which the weights of the edges are Euclidean distances between vertices.
