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

Yu A. Kochetov; A. A. Panin; A. V. Plyasunov

doi:10.1134/S0005117917030043

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

Yu A. Kochetov, A. A. Panin, A. V. Plyasunov

Research output: Contribution to journal › Article › peer-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 language	English
Pages (from-to)	425-434
Number of pages	10
Journal	Automation and Remote Control
Volume	78
Issue number	3
DOIs	https://doi.org/10.1134/S0005117917030043
Publication status	Published - 1 Mar 2017

Keywords

approximation
genetic algorithm
load balancing
local search

Access to Document

10.1134/S0005117917030043

Cite this

@article{41553bc3167d42878e3fd4d7ecb5c8d8,

title = "Genetic local search and hardness of approximation for the server load balancing problem",

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 = "approximation, genetic algorithm, load balancing, local search",

author = "Kochetov, {Yu A.} and Panin, {A. A.} and Plyasunov, {A. V.}",

year = "2017",

month = mar,

day = "1",

doi = "10.1134/S0005117917030043",

language = "English",

volume = "78",

pages = "425--434",

journal = "Automation and Remote Control",

issn = "0005-1179",

publisher = "Maik Nauka-Interperiodica Publishing",

number = "3",

}

TY - JOUR

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

AU - Kochetov, Yu A.

AU - Panin, A. A.

AU - Plyasunov, A. V.

PY - 2017/3/1

Y1 - 2017/3/1

N2 - 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.

AB - 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.

KW - approximation

KW - genetic algorithm

KW - load balancing

KW - local search

UR - http://www.scopus.com/inward/record.url?scp=85014934824&partnerID=8YFLogxK

U2 - 10.1134/S0005117917030043

DO - 10.1134/S0005117917030043

M3 - Article

AN - SCOPUS:85014934824

VL - 78

SP - 425

EP - 434

JO - Automation and Remote Control

JF - Automation and Remote Control

SN - 0005-1179

IS - 3

ER -

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

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this