We consider a common scenario in competitive location, where two competitors (providers) place their facilities (servers) on a network, and the users, which are modeled by the nodes of the network, can choose between the providers. We assume that each user has an inelastic demand, specified by a positive real weight. A user is fully served by a closest facility. The benefit (gain) of a competitor is his market share, i.e., the total weight (demand) of the users served at his facilities. In our scenario the two providers, called the leader and the follower, sequentially place p and r servers, respectively. After the leader selects the locations for his p servers, the follower will determine the optimal locations for his r servers, that maximize his benefit. An (r,p)‐centroid is a set of locations for the p servers of the leader, that will minimize the maximum gain of the follower who can establish r servers. In this paper we focus mainly on the cases where either the leader or the follower can establish only one facility, i.e., either p=1, or r=1. We consider two versions of the model. In the discrete case the facilities can be established only at the nodes, while in the absolute case they can be established anywhere on the network. For the (r,1)‐centroid problem, we show that it is strongly NP‐hard for a general graph, but can be approximated within a factor e/(e−1). On the other hand, when the graph is a tree, we provide strongly polynomial algorithms for the (r,p)‐centroid model, whenever p is fixed. For the (1,1)‐centroid problem on a general graph, we improve upon known results, and give the first strongly polynomial algorithm. The discrete (1,p)‐centroid problem has been known to be NP‐hard even for a subclass of series‐parallel graphs with pathwidth bounded by 6. In view of this result, we consider the discrete and absolute (1,p) centroid models on a tree, and present the first strongly polynomial algorithms. Further improvements are shown when the tree is a path.
