RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
General information
Latest issue
Archive
Impact factor
Guidelines for authors
Submit a manuscript

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Avtomat. i Telemekh.:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Avtomat. i Telemekh., 2017, Issue 3, Pages 51–62 (Mi at14731)  

This article is cited in 1 scientific paper (total in 1 paper)

Stochastic Systems, Queuing Systems

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

Yu. A. Kochetovab, A. A. Paninab, A. V. Plyasunovab

a Novosibirsk State University, Novosibirsk, Russia
b Sobolev Institute of Mathematics, Siberian Branch, Russian Academy of Sciences, Novosibirsk, Russia

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

Funding Agency Grant Number
Ministry of Education and Science of the Republic of Kazakhstan 0115PK00546
This work was supported by the Ministry of Science and Education of Kazakhstan, project no. 0115PK00546.


Full text: PDF file (632 kB)
References: PDF file   HTML file

English version:
Automation and Remote Control, 2017, 78:3, 425–434

Bibliographic databases:

Presented by the member of Editorial Board: А. А. Лазарев

Received: 22.05.2015

Citation: Yu. A. Kochetov, A. A. Panin, A. V. Plyasunov, “Genetic local search and hardness of approximation for the server load balancing problem”, Avtomat. i Telemekh., 2017, no. 3, 51–62; Autom. Remote Control, 78:3 (2017), 425–434

Citation in format AMSBIB
\Bibitem{KocPanPly17}
\by Yu.~A.~Kochetov, A.~A.~Panin, A.~V.~Plyasunov
\paper Genetic local search and hardness of approximation for the server load balancing problem
\jour Avtomat. i Telemekh.
\yr 2017
\issue 3
\pages 51--62
\mathnet{http://mi.mathnet.ru/at14731}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=3666085}
\elib{http://elibrary.ru/item.asp?id=28960578}
\transl
\jour Autom. Remote Control
\yr 2017
\vol 78
\issue 3
\pages 425--434
\crossref{https://doi.org/10.1134/S0005117917030043}
\isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000396338200004}
\scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-85014934824}


Linking options:
  • http://mi.mathnet.ru/eng/at14731
  • http://mi.mathnet.ru/eng/at/y2017/i3/p51

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    This publication is cited in the following articles:
    1. P. A. Kononova, Yu. A. Kochetov, “A local search algorithm for the single machine scheduling problem with setups and a storage”, J. Appl. Industr. Math., 13:2 (2019), 239–249  mathnet  crossref  crossref
  • Avtomatika i Telemekhanika
    Number of views:
    This page:133
    Full text:3
    References:19
    First page:25

     
    Contact us:
     Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2020