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.
Original language | English |
---|---|
Pages (from-to) | 425-434 |
Number of pages | 10 |
Journal | Automation and Remote Control |
Volume | 78 |
Issue number | 3 |
DOIs | |
Publication status | Published - 1 Mar 2017 |
Keywords
- approximation
- genetic algorithm
- load balancing
- local search