Volume 21, No 5, 2014, P. 54-66
A. A. Panin and A. V. Plyasunov
On complexity of bilevel problems of location and pricing
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.
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
Novosibirsk State University,
2 Pirogov St., 630090 Novosibirsk, Russia
e-mail: firstname.lastname@example.org, email@example.com