Email this article Genetic local search and hardness of approximation for the server load balancing problem
- Authors: Kochetov Y.A.1,2, Panin A.A.1,2, Plyasunov A.V.1,2
-
Affiliations:
- Novosibirsk State University
- Sobolev Institute of Mathematics, Siberian Branch
- Issue: Vol 78, No 3 (2017)
- Pages: 425-434
- Section: Stochastic Systems, Queueing Systems
- URL: https://ogarev-online.ru/0005-1179/article/view/150555
- DOI: https://doi.org/10.1134/S0005117917030043
- ID: 150555
Cite item
Open Access
Access granted
Subscription Access
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
About the authors
Yu. A. Kochetov
Novosibirsk State University; Sobolev Institute of Mathematics, Siberian Branch
Author for correspondence.
Email: jkochet@math.nsc.ru
Russian Federation, Novosibirsk; Novosibirsk
A. A. Panin
Novosibirsk State University; Sobolev Institute of Mathematics, Siberian Branch
Email: jkochet@math.nsc.ru
Russian Federation, Novosibirsk; Novosibirsk
A. V. Plyasunov
Novosibirsk State University; Sobolev Institute of Mathematics, Siberian Branch
Email: jkochet@math.nsc.ru
Russian Federation, Novosibirsk; Novosibirsk
Supplementary files
