Competitive facility location models
Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 49 (2009) no. 6, pp. 1037-1054
A. V. Kononov; Yu. A. Kochetov; A. V. Plyasunov. Competitive facility location models. Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 49 (2009) no. 6, pp. 1037-1054. http://geodesic.mathdoc.fr/item/ZVMMF_2009_49_6_a7/
@article{ZVMMF_2009_49_6_a7,
     author = {A. V. Kononov and Yu. A. Kochetov and A. V. Plyasunov},
     title = {Competitive facility location models},
     journal = {\v{Z}urnal vy\v{c}islitelʹnoj matematiki i matemati\v{c}eskoj fiziki},
     pages = {1037--1054},
     year = {2009},
     volume = {49},
     number = {6},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/ZVMMF_2009_49_6_a7/}
}
TY  - JOUR
AU  - A. V. Kononov
AU  - Yu. A. Kochetov
AU  - A. V. Plyasunov
TI  - Competitive facility location models
JO  - Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki
PY  - 2009
SP  - 1037
EP  - 1054
VL  - 49
IS  - 6
UR  - http://geodesic.mathdoc.fr/item/ZVMMF_2009_49_6_a7/
LA  - ru
ID  - ZVMMF_2009_49_6_a7
ER  - 
%0 Journal Article
%A A. V. Kononov
%A Yu. A. Kochetov
%A A. V. Plyasunov
%T Competitive facility location models
%J Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki
%D 2009
%P 1037-1054
%V 49
%N 6
%U http://geodesic.mathdoc.fr/item/ZVMMF_2009_49_6_a7/
%G ru
%F ZVMMF_2009_49_6_a7

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

Two classes of competitive facility location models are considered, in which several persons (players) sequentially or simultaneously open facilities for serving clients. The first class consists of discrete two-level programming models. The second class consists of game models with several independent players pursuing selfish goals. For the first class, its relationship with pseudo-Boolean functions is established and a novel method for constructing a family of upper and lower bounds on the optimum is proposed. For the second class, the tight PLS-completeness of the problem of finding Nash equilibriums is proved.

[1] Drezner Z., Klamroth K., Schobel A., Wesolowsky G., “The Weber problem”, Fac. Location. Applic. and Theory, Springer, Berlin, 2004, 1–36 | MR

[2] Beresnev V. L., Diskretnye zadachi razmescheniya i polinomy ot bulevykh peremennykh, In-t matem. SO RAN, Novosibirsk, 2005

[3] Chan Y., Location, transport and land-use. Modelling spatial-temporal information, Springer, Berlin, 2005

[4] Khachaturov V. P., Veselovskii B. E., Zlotov A. B. i dr., Kombinatornye metody i algoritmy resheniya zadach diskretnoi optimizatsii bolshoi razmernosti, Nauka, M., 2000 | MR | Zbl

[5] Eiselt H. A., Sandblom C.-L., Decision analysis, location models, and scheduling problems, Springer, Berlin, 2004 | Zbl

[6] P. B. Mirchandani, R. L. Francis (eds.), Discrete location theory, Wiley, Chichseter, 1990 | MR

[7] Beresnev V. L., Gimadi E. Kh., Dementev V. T., Ekstremalnye zadachi standartizatsii, Nauka, Novosibirsk, 1978 | MR

[8] Korte B., Vygen J., Combinatorial optimization. Theory and algorithms, Th. Ed., Springer, Berlin, 2005 | Zbl

[9] Schrijver A., Combinatorial optimization. Polyhedra and efficiency, Springer, Berlin, 2003

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

[11] Alekseeva E. B., Kochetov Yu. A., “Geneticheskii lokalnyi poisk dlya zadachi o $p$-mediane s predpochteniyami klientov”, Diskretnyi analiz i issl. operatsii. Ser. 2, 14:1 (2007), 3–31 | MR

[12] Gorbachevskaya L. E., Polinomialno razreshimye i NP-trudnye zadachi standartizatsii, Dis. $\dots$ kand. fiz.-matem. nauk, IM SO RAN, Novosibirsk, 1998

[13] Rodriquez C. M. C., Perez J. A. M., “Multiple voting location problems”, European J. Operat. Res., 191:2 (2008), 437–453 | DOI | MR

[14] Plastria F., Vanhaverbeke L., “Discrete models for competitive location with foresight”, Comput. and Operat. Res., 35:3 (2008), 683–700 | DOI | MR | Zbl

[15] Drezner T., Eiselt H. A., “Consumers in competitive location models”, Facility Location. Applic. and Theory, Springer, Berlin, 2004, 151–178 | MR

[16] Alekseeva E. V., Kochetova H. A., “Verkhnie i nizhnie otsenki dlya konkurentnoi zadachi o $p$-mediane”, Tr. XIV Baikalskoi mezhdunar. shkoly-seminara “Metody optimizatsii i ikh prilozh.”, T. 1, Severobaikalsk, 2008, 563–569

[17] Alekseeva E. V., Orlov A. B., “Geneticheskii algoritm dlya konkurentnoi zadachi o $p$-mediane”, Tr. XIV Baikalskoi mezhdunar. shkoly-seminara “Metody optimizatsii i ikh prilozh.”, T. 1, Severobaikalsk, 2008, 570–576

[18] Koutsoupias E., Papadimitriou C., “Worst-case equilibria”, Proc. XVI Ann. Symp. Theor. Aspects Comput. Sci., Trier, Germany, 1999, 404–413 | MR | Zbl

[19] Vetta A., Nash equilibria in competitive societies, with applications to facolity location, traffic routing and auctions, Proc. XLIII Ann. IEEE Symp. Foundations Comput. Sci. Vancouver, Canada, 2002, 416—425 | Zbl

[20] Kochetov Yu. A., Paschenko M. G., Plyasunov A. B., “O slozhnosti lokalnogo poiska v zadache o $p$-mediane”, Diskretnyi analiz i issl. operatsii. Ser. 2, 12:2 (2005), 44–71 | MR

[21] Kochetov Yu. A., “Ravnovesiya po Neshu v igrovykh modelyakh razmescheniya”, Tr. XIV Baikalskoi mezhdunar. shkoly-seminara “Metody optimizatsii i ikh prilozh.”, T. 1, Severobaikalsk, 2008, 119–127

[22] Tardos E., Wexler T., “Network formation games and the potential function method”, Algorithmic Game Theory, Cambridge Univ. Press, 2007, 487–516 | MR | Zbl

[23] Kochetov Yu. A., “Vychislitelnye vozmozhnosti lokalnogo poiska v kombinatornoi optimizatsii”, Zh. vychisl. matem. i matem. fiz., 48:5 (2008), 788–807 | MR | Zbl

[24] Yannakalis M., “Computational complexity”, Local Search in Combinatorial Optimizat., Wiley, Chichester, 1997, 19–55 | MR

[25] Vredeveld T., Lenstra J. K., “On local search for the generalized graph coloring problem”, Operat. Res. Letts., 31:4 (2003), 28–34 | DOI | MR | Zbl