Geodesic
On complexity of bilevel problems of location and pricing
Diskretnyj analiz i issledovanie operacij, Tome 21 (2014) no. 5, pp. 54-66.

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

We study complexity of bilevel problems with different pricing strategies: uniform, mill and discriminatory. It is shown that these problems are NP-hard in the strong sense, belong to Poly-APX class and are complete in its relative AP-reducibility. Bibliogr. 17.
Keywords: bilevel problem, location, pricing, computational and approximation complexity, NP-hard in the strong sense, AP-reducibility, Poly-APX-completeness. 
@article{DA_2014_21_5_a4,
     author = {A. A. Panin and A. V. Plyasunov},
     title = {On complexity of bilevel problems of location and pricing},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {54--66},
     publisher = {mathdoc},
     volume = {21},
     number = {5},
     year = {2014},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2014_21_5_a4/}
}
TY  - JOUR
AU  - A. A. Panin
AU  - A. V. Plyasunov
TI  - On complexity of bilevel problems of location and pricing
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2014
SP  - 54
EP  - 66
VL  - 21
IS  - 5
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2014_21_5_a4/
LA  - ru
ID  - DA_2014_21_5_a4
ER  - 
%0 Journal Article
%A A. A. Panin
%A A. V. Plyasunov
%T On complexity of bilevel problems of location and pricing
%J Diskretnyj analiz i issledovanie operacij
%D 2014
%P 54-66
%V 21
%N 5
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2014_21_5_a4/
%G ru
%F DA_2014_21_5_a4
A. A. Panin; A. V. Plyasunov. On complexity of bilevel problems of location and pricing. Diskretnyj analiz i issledovanie operacij, Tome 21 (2014) no. 5, pp. 54-66. http://geodesic.mathdoc.fr/item/DA_2014_21_5_a4/

[1] Geri M., Dzhonson D., Vychislitelnye mashiny i trudnoreshaemye zadachi, Mir, M., 1982, 416 pp. | MR

[2] Kochetov Yu. A., Plyasunov A. V., “Polinomialno razreshimyi klass zadach dvukhurovnevogo lineinogo programmirovaniya”, Diskret. analiz i issled. operatsii. Cer. 2, 4:2 (1997), 23–33 | MR

[3] Panin A. A., Plyasunov A. V., “The pricing problem. I: Exact and approximate algorithms”, J. Appl. Industr. Math., 7:2 (2013), 241–251 | DOI | MR

[4] Panin A. A., Plyasunov A. V., “The pricing problem. II: Computational complexity”, J. Appl. Industr. Math., 7:3 (2013), 420–430 | DOI | MR

[5] Aboolian R., Berman O., Krass D., “Competitive facility location model with concave demand”, Eur. J. Oper. Res., 181 (2007), 598–619 | DOI | MR | Zbl

[6] Aboolian R., Berman O., Krass D., “Optimizing pricing and location decisions for competitive service facilities charging uniform price”, J. Oper. Res. Soc., 59 (2008), 1506–1519 | DOI | Zbl

[7] Ausiello G., Crescenzi P., Gambosi G., Kann V., Marchetti-Spaccamela A., Protasi M., Complexity and approximation: combinatorial optimization problems and their aproximability properties, Springer-Verl., Berlin, 1999, 524 pp. | MR | Zbl

[8] Bazgan C., Escoffer B., Paschos V. Th., “Completeness in standard and differential approximation classes: Poly-(D)APX- and (D)PTAS-completeness”, Theor. Comput. Sci., 339 (2005), 272–292 | DOI | MR | Zbl

[9] Bouhtou M., Grigoriev A., Van Der Kraaij A. F., Van Hoesel S., Spieksma F., Uetz M., “Pricing bridges to cross a river”, Naval Res. Logistics, 54:4 (2007), 411–420 | DOI | MR | Zbl

[10] Crescenzi P., Kann V., Silvestri R., Trevisan L., “Structure in approximation classes”, SIAM J. Comput., 28:5 (1999), 1759–1782 | DOI | MR | Zbl

[11] Dasci A., Laporte G., “Location and pricing decisions of a multistore monopoly in a spatial market”, J. Region. Sci., 44 (2004), 489–515 | DOI

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

[13] Eiselt H. A., Marianov V., Foundations of location analysis, Springer-Verl., New York, 2011, 510 pp.

[14] Grigoriev A., van Loon J., Sviridenko M., Uetz M., Vredeveld T., “Optimal bundle pricing with monotonicity constraint”, Oper. Res. Lett., 36:5 (2008), 609–614 | DOI | MR | Zbl

[15] Hanjoul P., Hansen P., Peeters D., Thisse J.-F., “Uncapacitated plant location under alternative spatial price policies”, Market Sci., 36 (1990), 41–57 | MR | Zbl

[16] Serra D., ReVelle C., “Competitive locations and pricing on networks”, Geograph. Anal., 31 (1999), 109–129 | DOI

[17] Vives X., Oligopoly pricing: old ideas and new tools, MIT Press, Cambridge, MA, 1999, 425 pp.