Genetic local search and hardness of approximation for the server load balancing problem

Research output: Contribution to journalArticlepeer-review

3 Citations (Scopus)

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 languageEnglish
Pages (from-to)425-434
Number of pages10
JournalAutomation and Remote Control
Volume78
Issue number3
DOIs
Publication statusPublished - 1 Mar 2017

Keywords

  • approximation
  • genetic algorithm
  • load balancing
  • local search

Fingerprint

Dive into the research topics of 'Genetic local search and hardness of approximation for the server load balancing problem'. Together they form a unique fingerprint.

Cite this