А. В. Плясунов, А. А. Панин, “Задача ценообразования. Часть 2. Вычислительная сложность”, Дискретн. анализ и исслед. опер., 2012, том 19, выпуск 6,страницы 56

Эта публикация цитируется в 16 статьях

Задача ценообразования. Часть 2. Вычислительная сложность

А. В. Плясунов^ab, А. А. Панин^ba

^a Новосибирский гос. университет, Новосибирск, Россия
^b Институт математики им. С. Л. Соболева СО РАН, Новосибирск, Россия

Аннотация: Показано, что исследуемая задача принадлежит классу Log-APX, не может быть аппроксимируема с абсолютной погрешностью, ограниченной константой, и связанная с ней задача оценивания нетривиальна в классе $\Delta^p_2$. Приведены два полиномиально разрешимых случая задачи. Библиогр. 8.

Ключевые слова: вычислительная сложность, аппроксимируемость, двухуровневая задача, задача ценообразования, приближённый алгоритм, класс аппроксимируемости, NP-трудность в сильном смысле, полиномиальная иерархия.

УДК: 519.87+519.854

Статья поступила: 01.06.2011
Переработанный вариант: 04.06.2012