Volume 19, No 6, 2012, P. 5671
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 LogAPX, cannot be approximable with an absolute error limited by a constant, and the corresponding evaluation problem is nontrivial 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, NPhard 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
email: apljas@math.nsc.ru, arteam1897@gmail.com
