On the complexity of the (r|p)-centroid problem in the plane Full article
| Journal |
TOP
ISSN: 1134-5764 , E-ISSN: 1863-8279 |
||
|---|---|---|---|
| Output data | Year: 2014, Volume: 22, Number: 2, Pages: 614-624 Pages count : 11 DOI: 10.1007/s11750-013-0275-y | ||
| Tags | Bilevel programming; Competitive location; Leader-Follower problem | ||
| Authors |
|
||
| Affiliations |
|
Abstract:
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 Σ^P_2 -hard. Moreover, we strengthen the previous results for the discrete case and networks. We show that the game is Σ^P_2 -hard even for planar graphs for which the weights of the edges are Euclidean distances between vertices.
Cite:
Davydov I.
, Kochetov Y.
, Plyasunov A.
On the complexity of the (r|p)-centroid problem in the plane
TOP. 2014. V.22. N2. P.614-624. DOI: 10.1007/s11750-013-0275-y WOS Scopus OpenAlex
On the complexity of the (r|p)-centroid problem in the plane
TOP. 2014. V.22. N2. P.614-624. DOI: 10.1007/s11750-013-0275-y WOS Scopus OpenAlex
Identifiers:
| Web of science: | WOS:000339344400015 |
| Scopus: | 2-s2.0-84904175678 |
| OpenAlex: | W2114002675 |