Genetic local search and hardness of approximation for the server load balancing problem
Yury Kochetov, Artem A. Panin, A. V. Plyasunov · Automation and Remote Control · 2017
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.