On the complexity of the (r|p)-centroid problem in the plane

Ivan Davydov, Yury Kochetov () and Alexandr Plyasunov

TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, 2014, vol. 22, issue 2, 614-623

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 $\varSigma_{2}^{P}$ -hard. Moreover, we strengthen the previous results for the discrete case and networks. We show that the game is $\varSigma_{2}^{P}$ -hard even for planar graphs for which the weights of the edges are Euclidean distances between vertices. Copyright Sociedad de Estadística e Investigación Operativa 2014

Keywords: Competitive location; Bilevel programming; Leader–Follower problem; 90B80; 90C05; 90C27 (search for similar items in EconPapers)
Date: 2014
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://hdl.handle.net/10.1007/s11750-013-0275-y (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:topjnl:v:22:y:2014:i:2:p:614-623

Ordering information: This journal article can be ordered from
http://link.springer.de/orders.htm

DOI: 10.1007/s11750-013-0275-y

Access Statistics for this article

TOP: An Official Journal of the Spanish Society of Statistics and Operations Research is currently edited by Juan José Salazar González and Gustavo Bergantiños

More articles in TOP: An Official Journal of the Spanish Society of Statistics and Operations Research from Springer, Sociedad de Estadística e Investigación Operativa
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().