Enviar artigo por via de e-mail Genetic local search and hardness of approximation for the server load balancing problem
- Autores: Kochetov Y.A.1,2, Panin A.A.1,2, Plyasunov A.V.1,2
-
Afiliações:
- Novosibirsk State University
- Sobolev Institute of Mathematics, Siberian Branch
- Edição: Volume 78, Nº 3 (2017)
- Páginas: 425-434
- Seção: Stochastic Systems, Queueing Systems
- URL: https://ogarev-online.ru/0005-1179/article/view/150555
- DOI: https://doi.org/10.1134/S0005117917030043
- ID: 150555
Citar
Acesso aberto
Acesso está concedido
Somente assinantes
Resumo
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.
Palavras-chave
Sobre autores
Yu. Kochetov
Novosibirsk State University; Sobolev Institute of Mathematics, Siberian Branch
Autor responsável pela correspondência
Email: jkochet@math.nsc.ru
Rússia, Novosibirsk; Novosibirsk
A. Panin
Novosibirsk State University; Sobolev Institute of Mathematics, Siberian Branch
Email: jkochet@math.nsc.ru
Rússia, Novosibirsk; Novosibirsk
A. Plyasunov
Novosibirsk State University; Sobolev Institute of Mathematics, Siberian Branch
Email: jkochet@math.nsc.ru
Rússia, Novosibirsk; Novosibirsk
Arquivos suplementares
