Wednesday, 15:45 - 16:10 h, Room: H 3008


Yury Kochetov
A local search algorithm for the (r | p)-centroid problem on the plane

Coauthors: Emilio Carrizosa, Ivan A. Davydov, Alexandr V. Plyasunov


In the (r | p)-centroid problem two players, leader and
follower, open facilities to service clients. We assume that clients are on the Euclidean plane and facilities can be opened in arbitrary points on the plane. Leader opens p facilities. Later on, follower opens r facilities. Each client patronizes the closest facility. Our goal is to find p facilities for the leader to maximize his market share. We show that the problem is Σ2P-hard. In other words, this Stackelberg game is more difficult than well-known
NP-complete problems, unless P=NP. To find near optimal solutions we develop a local search heuristic, based on the exact approach for the follower problem. We apply discretization of the (r | Xp-1+1)-centroid problem where the leader can move one facility only in order to identify the best neighboring solution. Starting solution is generated by a new alternating heuristic and an exact
polynomial time algorithm for the (1 | 1)-centroid problem. Computational experiments for the randomly generated test instances show that this local search algorithm dominates the previous heuristics.


Talk 2 of the contributed session Wed.3.H 3008
"Competitive and multi-objective facility location" [...]
Cluster 2
"Combinatorial optimization" [...]


  online loans . When the problem is not treated, it can ruin intimate life of couples and destroy their relationships. Viagra Professional was produces not to let this happen. Professional means highly qualified. It strikes the target and doesn't allow a disorder to occupy man's body.