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

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