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

Standard

Genetic local search and hardness of approximation for the server load balancing problem. / Kochetov, Yu A.; Panin, A. A.; Plyasunov, A. V.

в: Automation and Remote Control, Том 78, № 3, 01.03.2017, стр. 425-434.

Результаты исследований: Научные публикации в периодических изданиях › статья › Рецензирование

BibTeX

@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",

}

RIS

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 -

ID: 9031965