Volume 19, No 6, 2012, P. 56-71

UDC 519.87+519.854
A. V. Plyasunov, A. A. Panin
The pricing problem. Part 2. The computational complexity

Abstract:
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.
Bibliogr. 8.

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
2. Novosibirsk State University,
2 Pirogov St., 630090 Novosibirsk, Russia
e-mail: apljas@math.nsc.ru, arteam1897@gmail.com