|
Diskretnyi Analiz i Issledovanie Operatsii, 2012, Volume 19, Issue 6, Pages 56–71
(Mi da712)
|
|
|
|
This article is cited in 16 scientific papers (total 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.
Received: 01.06.2011 Revised: 04.06.2012
Citation:
A. V. Plyasunov, A. A. Panin, “The pricing problem. Part 2. The computational complexity”, Diskretn. Anal. Issled. Oper., 19:6 (2012), 56–71; J. Appl. Industr. Math., 7:3 (2013), 420–430
Linking options:
https://www.mathnet.ru/eng/da712 https://www.mathnet.ru/eng/da/v19/i6/p56
|
Statistics & downloads: |
Abstract page: | 364 | Full-text PDF : | 128 | References: | 34 | First page: | 2 |
|