Том 19, номер 6, 2012 г., Стр. 56-71

УДК 519.87+519.854
Плясунов А. В., Панин А. В.
Задача ценообразования. Часть 2. Вычислительная сложность

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

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

Плясунов Александр Владимирович ^1,2
Панин Артём Александрович ^1,2
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
2. Новосибирский гос. университет,
ул. Пирогова, 2, 630090 Новосибирск, Россия
е-mail: apljas@math.nsc.ru, arteam1897@gmail.com

Статья поступила 1 июня 2011 г.
Исправленный вариант — 4 июня 2012 г.

Литература

[1] Панин А. А., Плясунов А. В. Задача ценообразования. Часть 1: точные и приближённые алгоритмы решения // Дискрет. анализ и исслед. операций. — 2012. — Т. 19, № 5. — С. 83–100.

[2] Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. — М.: Мир. 1982. — 416 с.

[3] Схрейвер А. Теория линейного и целочисленного программирования. Т. 1. — М.: Мир, 1991. — 360 с.

[4] Attallah M. Algorithms and theory of computation handbook. — Boca Raton: CRC Press LLC, 1999. — 1312 p.

[5] Ausiello G., Crescenzi P., Gambosi G., Kann V., Marchetti-Spaccamela A., Protasi M. Complexity and approximation: combinatorial opti?mization problems and their aproximability properties. — Berlin: Springer-Verl., 1999. — 524 p.

[6] Dempe S. J. Foundations of bilevel programming. — Dordrecht: Kluwer Acad. Publ., 2002. — 320 p.

[7] Hanjoul P., Hansen P., Peeters D., Thisse J.-F. Uncapacitated plant location under alternative spatial price policies // Market Sci. — 1990. — Vol. 36. — P. 41–57.

[8] Leggette E.W., Jr., Moore D. J. Optimization problems and the polynomial hierarchy // Theor. Comput. Sci. — 1981. — Vol. 15, N 3. — P. 279–289.