|
Дискретный анализ и исследование операций, 2014, том 21, выпуск 5, страницы 54–66
(Mi da793)
|
|
|
|
Эта публикация цитируется в 8 научных статьях (всего в 8 статьях)
О сложности двухуровневых задач размещения и ценообразования
А. А. Панинab, А. В. Плясуновab a Институт математики им. С. Л. Соболева СО РАН, пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
b Новосибирский гос. университет, ул. Пирогова, 2, 630090 Новосибирск, Россия
Аннотация:
Рассматриваются двухуровневые частично-целочисленные задачи размещения и ценообразования. Каждая из них определяется оптимизационными задачами верхнего и нижнего уровней, первая из которых описывает выбор размещения и ценообразования, а вторая моделирует реакцию потребителей на решение верхнего уровня. Основные усилия в работе концентрируются вокруг изучения вычислительной сложности двухуровневых задач с разными стратегиями ценообразования: равномерной, фабричной и дискриминационной. Показано, что при любой стратегии ценообразования соответствующая оптимизационная задача NP-трудна в сильном смысле, принадлежит классу Poly-APX и является полной в нём относительно AP-сводимости. Библиогр. 17.
Ключевые слова:
двухуровневая задача, размещение, ценообразование, вычислительная и аппроксимационная сложности, NP-трудность в сильном смысле, AP-сводимость, Poly-APX-полнота.
Статья поступила: 15.10.2013 Переработанный вариант: 29.01.2014
Образец цитирования:
А. А. Панин, А. В. Плясунов, “О сложности двухуровневых задач размещения и ценообразования”, Дискретн. анализ и исслед. опер., 21:5 (2014), 54–66; J. Appl. Industr. Math., 8:4 (2014), 574–581
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/da793 https://www.mathnet.ru/rus/da/v21/i5/p54
|
Статистика просмотров: |
Страница аннотации: | 284 | PDF полного текста: | 104 | Список литературы: | 49 | Первая страница: | 15 |
|