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

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

Journal

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

Output data

Year: 2017, Number: 3, Pages: 51-62 Pages count : 12

Authors

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

Affiliations

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

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

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

Submitted:

May 22, 2015

No identifiers

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