Geodesic
Computational complexity of the discrete competitive facility location problem
Diskretnyj analiz i issledovanie operacij, Tome 21 (2014) no. 4, pp. 62-79.

Voir la notice de l'article provenant de la source Math-Net.Ru

We consider the discrete competitive facility location problem where a finite set of clients and a finite set of candidate sites are given. Two competing firms successively open their facilities with the goal to maximize the profit from serving the clients. Each client chooses only one facility to be served by according to his known preferences. We determine the computational complexity of the problem in two special cases. Bibliogr. 16.
Keywords: polynomial hierarchy, Stackelberg game, bilevel programming. 
@article{DA_2014_21_4_a6,
     author = {A. A. Mel'nikov},
     title = {Computational complexity of the discrete competitive facility location problem},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {62--79},
     publisher = {mathdoc},
     volume = {21},
     number = {4},
     year = {2014},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2014_21_4_a6/}
}
TY  - JOUR
AU  - A. A. Mel'nikov
TI  - Computational complexity of the discrete competitive facility location problem
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2014
SP  - 62
EP  - 79
VL  - 21
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2014_21_4_a6/
LA  - ru
ID  - DA_2014_21_4_a6
ER  - 
%0 Journal Article
%A A. A. Mel'nikov
%T Computational complexity of the discrete competitive facility location problem
%J Diskretnyj analiz i issledovanie operacij
%D 2014
%P 62-79
%V 21
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2014_21_4_a6/
%G ru
%F DA_2014_21_4_a6
A. A. Mel'nikov. Computational complexity of the discrete competitive facility location problem. Diskretnyj analiz i issledovanie operacij, Tome 21 (2014) no. 4, pp. 62-79. http://geodesic.mathdoc.fr/item/DA_2014_21_4_a6/

[1] Beresnev V. L., “Upper bounds for objective functions of discrete competitive facility location problems”, J. Appl. Industr. Math., 3:4 (2009), 419–432 | DOI | MR | Zbl

[2] Beresnev V. L., “Local search algorithms for the problem of competitive location of enterprises”, Autom. Remote Control, 73:3 (2012), 425–439 | DOI | MR

[3] Beresnev V. L., Goncharov E. N., Mel'nikov A. A., “Local search with a generalized neighborhood in the optimization problem for pseudo-Boolean functions”, J. Appl. Industr. Math., 6:1 (2012), 22–30 | DOI | MR | Zbl

[4] Beresnev V. L., Melnikov A. A., “Approximate algorithms for the competitive facility location problems”, J. Appl. Industr. Math., 5:2 (2011), 180–190 | DOI | MR | Zbl

[5] Vasil'ev I. L., Klimentova K. B., “The branch and cut method for the facility location problem with clients' preferences”, J. Appl. Industr. Math., 4:3 (2010), 441–454 | DOI | MR | Zbl

[6] Vasil'ev I. L., Klimentova K. B., Kochetov Yu. A., “New lower bounds for the facility location problem with clients' preferences”, Comput. Math. Math. Phys., 49:6 (2009), 1010–1020 | DOI | MR | Zbl

[7] Germeier Yu. B., Igry s neprotivopolozhnymi interesami, Nauka, M., 1976, 328 pp. | MR

[8] Kononov A. V., Kochetov Yu. A., Plyasunov A. V., “Competitive facility location models”, Comput. Math. Math. Phys., 49:6 (2009), 994–1009 | DOI | MR | Zbl

[9] Beresnev V., “Branch-and-bound algorithm for competitive facility location problem”, Comput. Oper. Res., 40 (2013), 2062–2070 | DOI | MR

[10] Canovas L., Garcia S., Labbe M., Marin A., “A strengthened formulation for the simple plant location problem with order”, Oper. Res. Lett., 35 (2007), 141–150 | DOI | MR | Zbl

[11] Davydov I., Kochetov Yu., Plyasunov A., “On the complexity of the ($r|p$)-centroid problem in the plane”, TOP, 22:2 (2014), 614–623 | DOI

[12] Dempe S., Foundations of bilevel programming, Kluwer Acad. Publ., Dordrecht, 2002, 332 pp. | MR | Zbl

[13] Garey M. R., Johnson D. S., Computers and intractability: a guide to the theory of NP-completeness, W. H. Freeman Co., San Francisco, 1979, 338 pp. | MR | Zbl

[14] Krarup J., Pruzan P. M., “The simple plant location problem: survey and synthesis”, Eur. J. Oper. Res., 12 (1983), 36–81 | DOI | MR | Zbl

[15] Stackelberg H., The theory of the market economy, Oxford Univ. Press, Oxford, 1952, 289 pp.

[16] Stockmeyer L. J., “The polynomial-time hierarchy”, Theor. Comput. Sci., 3 (1976), 1–22 | DOI | MR