License
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2013.461
URN: urn:nbn:de:0030-drops-43936
URL: http://drops.dagstuhl.de/opus/volltexte/2013/4393/
Go to the corresponding LIPIcs Volume Portal


Khodamoradi, Kamyar ; Krishnamurti, Ramesh ; Rafiey, Arash ; Stamoulis, Georgios

PTAS for Ordered Instances of Resource Allocation Problems

pdf-format:
35.pdf (0.6 MB)


Abstract

We consider the problem of fair allocation of indivisible goods where we are given a set I of m indivisible resources (items) and a set P of n customers (players) competing for the resources. Each resource j in I has a same value vj > 0 for a subset of customers interested in j and it has no value for other customers. The goal is to find a feasible allocation of the resources to the interested customers such that in the Max-Min scenario (also known as Santa Claus problem) the minimum utility (sum of the resources) received by each of the customers is as high as possible and in the Min-Max case (also known as R||C_max problem), the maximum utility is as low as possible. In this paper we are interested in instances of the problem that admit a PTAS. These instances are not only of theoretical interest but also have practical applications. For the Max-Min allocation problem, we start with instances of the problem that can be viewed as a convex bipartite graph; there exists an ordering of the resources such that each customer is interested (has positive evaluation) in a set of consecutive resources and we demonstrate a PTAS. For the Min-Max allocation problem, we obtain a PTAS for instances in which there is an ordering of the customers (machines) and each resource (job) is adjacent to a consecutive set of customers (machines). Next we show that our method for the Max-Min scenario, can be extended to a broader class of bipartite graphs where the resources can be viewed as a tree and each customer is interested in a sub-tree of a bounded number of leaves of this tree (e.g. a sub-path).

BibTeX - Entry

@InProceedings{khodamoradi_et_al:LIPIcs:2013:4393,
  author =	{Kamyar Khodamoradi and Ramesh Krishnamurti and Arash Rafiey and Georgios Stamoulis},
  title =	{{PTAS for Ordered Instances of Resource Allocation Problems}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)},
  pages =	{461--473},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-64-4},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{24},
  editor =	{Anil Seth and Nisheeth K. Vishnoi},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2013/4393},
  URN =		{urn:nbn:de:0030-drops-43936},
  doi =		{10.4230/LIPIcs.FSTTCS.2013.461},
  annote =	{Keywords: Approximation Algorithms, Convex Bipartite Graphs, Resource Allocation}
}

Keywords: Approximation Algorithms, Convex Bipartite Graphs, Resource Allocation
Seminar: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)
Issue Date: 2013
Date of publication: 09.12.2013


DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI