RUS  ENG
Full version
JOURNALS // Diskretnyi Analiz i Issledovanie Operatsii // Archive

Diskretn. Anal. Issled. Oper., 2012 Volume 19, Issue 6, Pages 56–71 (Mi da712)

This article is cited in 16 papers

The pricing problem. Part 2. The computational complexity

A. V. Plyasunovab, A. A. Paninba

a Novosibirsk State University, Novosibirsk, Russia
b Sobolev Institute of Mathematics, Novosibirsk, Russia

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.

UDC: 519.87+519.854

Received: 01.06.2011
Revised: 04.06.2012


 English version:
Journal of Applied and Industrial Mathematics, 2013, 7:3, 420–430

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024