Volume 19, No 6, 2012, P. 56-71
A. V. Plyasunov, A. A. Panin
The pricing problem. Part 2. The computational complexity
For the problem, it is shown that it belongs to the class Log-APX, cannot be approximable with an absolute error limited by a constant, and the corresponding evaluation problem is non-trivial in the class $\Delta^p_2$. Also, two polynomial solvable cases of the problem are provided.
Keywords: computational complexity, approximability, the bilevel pricing problem, approximate algorithm, approximability class, NP-hard in the strong sense, polynomial hierarchy.
Plyasunov Alexander Vladimirovich 1,2
Panin Artyom Alexandrovich 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: email@example.com, firstname.lastname@example.org