1 Search Results for "Köhler, Sven"

Document

DOI: 10.4230/LIPIcs.OPODIS.2015.11

Distributed Approximation of k-Service Assignment

Authors: Magnús M. Halldórsson, Sven Köhler, and Dror Rawitz

Published in: LIPIcs, Volume 46, 19th International Conference on Principles of Distributed Systems (OPODIS 2015)

Abstract

We consider the k-Service Assignment problem (k-SA), 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 r-restricted version of k-SA, no client requires more than an r-fraction of the capacity of any adjacent server. The k-SA 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+1-r)/(1-r)-approximation algorithm for r-restricted k-SA. 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)^2-approximation algorithm for k-SA. In the distributed setting, we present: (i) a (1+epsilon)*(k +1-r)/(1-r)-approximation algorithm for r-restricted k-SA, (ii) a (1+epsilon)(k+1)-approximation algorithm that uses a resource augmentation factor of 1+r for r-restricted k-SA, both for any constant epsilon>0, and (iii) an O{k^2}-approximation algorithm for k-SA (in expectation). The three distributed algorithms compute a solution with high probability and terminate in O(k^2 *log^3(n)) rounds.

Cite as

Magnús M. Halldórsson, Sven Köhler, and Dror Rawitz. Distributed Approximation of k-Service Assignment. In 19th International Conference on Principles of Distributed Systems (OPODIS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 46, pp. 11:1-11:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{halldorsson_et_al:LIPIcs.OPODIS.2015.11,
  author =	{Halld\'{o}rsson, Magn\'{u}s M. and K\"{o}hler, Sven and Rawitz, Dror},
  title =	{{Distributed Approximation of k-Service Assignment}},
  booktitle =	{19th International Conference on Principles of Distributed Systems (OPODIS 2015)},
  pages =	{11:1--11:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-98-9},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{46},
  editor =	{Anceaume, Emmanuelle and Cachin, Christian and Potop-Butucaru, Maria},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2015.11},
  URN =		{urn:nbn:de:0030-drops-66024},
  doi =		{10.4230/LIPIcs.OPODIS.2015.11},
  annote =	{Keywords: approximation algorithms, distributed algorithms, related machines}
}

Refine by Author
1 Halldórsson, Magnús M.
1 Köhler, Sven
1 Rawitz, Dror

Refine by Classification

Refine by Keyword
1 approximation algorithms
1 distributed algorithms
1 related machines

Refine by Type
1 document

Refine by Publication Year
1 2016

1 Search Results for "Köhler, Sven"

Distributed Approximation of k-Service Assignment

Abstract

Cite as

Thanks for your feedback!

Could not send message