Premium
The load‐distance balancing problem
Author(s) -
Bortnikov Edward,
Khuller Samir,
Li Jian,
Mansour Yishay,
Naor Joseph Seffi
Publication year - 2012
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.20477
Subject(s) - server , computer science , set (abstract data type) , function (biology) , load balancing (electrical power) , approximation algorithm , network delay , stability (learning theory) , regular polygon , mathematical optimization , computer network , algorithm , mathematics , geometry , evolutionary biology , machine learning , network packet , biology , programming language , grid
Problems dealing with assignment of clients to servers have been widely studied. However, they usually do not model the fact that the delay incurred by a client is a function of both the distance to the assigned server and the load on this server, under a given assignment. We study a problem referred to as the load‐distance balancing (LDB) problem, where the objective is assigning a set of clients to a set of given servers. Each client suffers a delay, that is, the sum of the network delay (which is proportional to the distance to its server) and the congestion delay at this server, a nondecreasing function of the number of clients assigned to the server. We address two flavors of LDB—the first one seeking to minimize the maximum incurred delay, and the second one targeted for minimizing the average delay. For the first variation, we present hardness results, a best possible approximation algorithm, and an optimal algorithm for a special case of linear placement of clients and servers. For the second one, we show the problem is NP‐hard in general, and present a 2‐approximation for concave delay functions and an exact algorithm, if the delay function is convex. We also consider the game theoretic version of the second problem and show the price of stability of the game is at most 2 and at least 4/3. © 2011 Wiley Periodicals, Inc. NETWORKS, 2012