Halldórsson, Magnús M. ;
Köhler, Sven ;
Rawitz, Dror
Distributed Approximation of kService Assignment
Abstract
We consider the kService Assignment problem (kSA), defined as follows. The input consists of a network that contains servers and clients, and an integer k. Each server has a finite capacity, and each client is associated with a demand and a profit. A feasible solution is an assignment of clients to neighboring servers such that (i) the total demand assigned to a server is at most its capacity, and (ii) a client is assigned either to k servers or to none. The profit of an assignment is the total profit of clients that are assigned to k servers, and the goal is to find a maximum profit assignment. In the rrestricted version of kSA, no client requires more than an rfraction of the capacity of any adjacent server. The kSA problem is motivated by backup placement in networks and by resource allocation in 4G cellular networks. It can also be viewed as machine scheduling on related machines with assignment restrictions.
We present a centralized polynomial time greedy (k+1r)/(1r)approximation algorithm for rrestricted kSA. We then show that a variant of this algorithm achieves an approximation ratio of k+1 using a resource augmentation factor of 1+r. We use the latter to present a (k+1)^2approximation algorithm for kSA. In the distributed setting, we present: (i) a (1+epsilon)*(k +1r)/(1r)approximation algorithm for rrestricted kSA, (ii) a (1+epsilon)(k+1)approximation algorithm that uses a resource augmentation factor of 1+r for rrestricted kSA, both for any constant epsilon>0, and (iii) an O{k^2}approximation algorithm for kSA (in expectation). The three distributed algorithms compute a solution with high probability and terminate in O(k^2 *log^3(n)) rounds.
BibTeX  Entry
@InProceedings{halldrsson_et_al:LIPIcs:2016:6602,
author = {Magn{\'u}s M. Halld{\'o}rsson and Sven K{\"o}hler and Dror Rawitz},
title = {{Distributed Approximation of kService Assignment}},
booktitle = {19th International Conference on Principles of Distributed Systems (OPODIS 2015)},
pages = {116},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897989},
ISSN = {18688969},
year = {2016},
volume = {46},
editor = {Emmanuelle Anceaume and Christian Cachin and Maria PotopButucaru},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6602},
URN = {urn:nbn:de:0030drops66024},
doi = {10.4230/LIPIcs.OPODIS.2015.11},
annote = {Keywords: approximation algorithms, distributed algorithms, related machines}
}
2016
Keywords: 

approximation algorithms, distributed algorithms, related machines 
Seminar: 

19th International Conference on Principles of Distributed Systems (OPODIS 2015)

Issue date: 

2016 
Date of publication: 

2016 