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 MaxMin 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 MinMax case (also known as RC_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 MaxMin 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 MinMax 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 MaxMin 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 subtree of a bounded number of leaves of this tree (e.g. a subpath).
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 = {461473},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897644},
ISSN = {18688969},
year = {2013},
volume = {24},
editor = {Anil Seth and Nisheeth K. Vishnoi},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2013/4393},
URN = {urn:nbn:de:0030drops43936},
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 