|
Avtomatika i Telemekhanika, 2017, Issue 3, Pages 51–62
(Mi at14731)
|
|
|
|
This article is cited in 4 scientific papers (total in 4 papers)
Stochastic Systems, Queuing Systems
Genetic local search and hardness of approximation for the server load balancing problem
Yu. A. Kochetovab, A. A. Paninab, A. V. Plyasunovab a Novosibirsk State University, Novosibirsk, Russia
b Sobolev Institute of Mathematics, Siberian Branch, Russian Academy of Sciences, Novosibirsk, Russia
Abstract:
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.
Keywords:
load balancing, local search, genetic algorithm, approximation.
Citation:
Yu. A. Kochetov, A. A. Panin, A. V. Plyasunov, “Genetic local search and hardness of approximation for the server load balancing problem”, Avtomat. i Telemekh., 2017, no. 3, 51–62; Autom. Remote Control, 78:3 (2017), 425–434
Linking options:
https://www.mathnet.ru/eng/at14731 https://www.mathnet.ru/eng/at/y2017/i3/p51
|
|