Volume 21, No 5, 2014, P. 54-66

UDC 519.87+519.854
A. A. Panin and A. V. Plyasunov
On complexity of bilevel problems of location and pricing

Abstract:
We study omplexity 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.

Panin Artem Alexandrovich ^1,2
Plyasunov Alexander Vladimirovich ^1,2
1. S. L. Sobolev Institute of Mathematics, SB RAS,
4 Acad. Koptyug Ave., 630090 Novosibirsk, Russia
2. Novosibirsk State University,
2 Pirogov St., 630090 Novosibirsk, Russia
e-mail: arteam1897@gmail.com, apljas@math.nsc.ru