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
|