Genetic local search and hardness of approximation for the server load balancing problem

Yu. A. Kochetov; A. A. Panin; A. V. Plyasunov

doi:10.1134/S0005117917030043

Genetic local search and hardness of approximation for the server load balancing problem

Авторы: Kochetov Y.A.¹^,2, Panin A.A.¹^,2, Plyasunov A.V.¹^,2
Учреждения:
1. Novosibirsk State University
2. Sobolev Institute of Mathematics, Siberian Branch
Выпуск: Том 78, № 3 (2017)
Страницы: 425-434
Раздел: Stochastic Systems, Queueing Systems
URL: https://journals.rcsi.science/0005-1179/article/view/150555
DOI: https://doi.org/10.1134/S0005117917030043
ID: 150555

Цитировать

Полный текст

Открытый доступ
Доступ закрыт

Доступ предоставлен
Доступ закрыт

Только для подписчиков

Аннотация
Об авторах
Список литературы
Дополнительные файлы
Статистика

Аннотация

We consider a well-known NP-hard server load balancing problem. We study the computational complexity of finding approximate solutions with guaranteed accuracy estimate. We show that this problem is Log-APX-hard with respect to PTAS reductions. To solve the problem, we develop an approximate method based on the ideas of genetic local search. We show results of computational experiments.