Реферат: 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.

Библиографическая ссылка: 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

Идентификаторы БД:

Web of science:	WOS:000339344400015
Scopus:	2-s2.0-84904175678
OpenAlex:	W2114002675

Цитирование в БД:

БД	Цитирований
Scopus	32
OpenAlex	32
Web of science	14

Альметрики: