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

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

2 Цитирования (Scopus)

Аннотация

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.

Язык оригинала	английский
Страницы (с-по)	425-434
Число страниц	10
Журнал	Automation and Remote Control
Том	78
Номер выпуска	3
DOI	https://doi.org/10.1134/S0005117917030043
Состояние	Опубликовано - 1 мар 2017

Доступ к документу

10.1134/S0005117917030043

Link to publication in Scopus

Fingerprint Подробные сведения о темах исследования «Genetic local search and hardness of approximation for the server load balancing problem». Вместе они формируют уникальный семантический отпечаток (fingerprint).

Цитировать

Kochetov, Y. A., Panin, A. A., & Plyasunov, A. V. (2017). Genetic local search and hardness of approximation for the server load balancing problem. Automation and Remote Control, 78(3), 425-434. https://doi.org/10.1134/S0005117917030043

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