Geodesic
Competitive facility location models
Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 49 (2009) no. 6, pp. 1037-1054 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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. 
@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
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/

[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