Генетический локальный поиск и сложность аппроксимации задачи балансировки нагрузки на серверы | Sciact - Система учета научной деятельности ИМ СО РАН

Генетический локальный поиск и сложность аппроксимации задачи балансировки нагрузки на серверы Научная публикация

Журнал

Журнал вычислительной математики и математической физики
ISSN: 0044-4669

Вых. Данные

Год: 2017, Номер: 3, Страницы: 51-62 Страниц : 12

Авторы

Кочетов Ю.А. ^1,2 , Панин А.А. ^1,2 , Плясунов А.В. ^1,2

Организации

1	Институт математики им. С.Л. Соболева СО РАН, Новосибирск
2	Новосибирский государственный университет

Рассматривается известная NP-трудная задача балансировки нагрузки на серверы. Исследуется вычислительная сложность получения приближенных решений с гарантированной оценкой точности. Показано, что задача является Log-APX-трудной относительно PTAS-сводимости. Для решения задачи разработан приближенный метод, основанный на идеях генетического локального поиска. Приводятся результаты вычислительных экспериментов

Кочетов Ю.А. , Панин А.А. , Плясунов А.В.
Генетический локальный поиск и сложность аппроксимации задачи балансировки нагрузки на серверы
Журнал вычислительной математики и математической физики. 2017. №3. С.51-62.

Поступила в редакцию:

22 мая 2015 г.

Нет идентификаторов

Пока нет цитирований