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.