Paper Info
Title
PTAS for Ordered Instances of Resource Allocation Problems with Restrictions on Inclusions.
Abstract
We consider the problem of allocating a set $I$ of $m$ indivisible resources (items) to a set $P$ of $n$ customers (players) competing for the resources. Each resource $j I$ has a same value $v_j u003e 0$ for a subset of customers interested in $j$, and zero value for the remaining customers. The utility received by each customer is the sum of the values of the resources allocated to her. The goal is to find a feasible allocation of the resources to the interested customers such that for the Max-Min allocation problem (Min-Max allocation problem) the minimum of the utilities (maximum of the utilities) received by the customers is maximized (minimized). The Max-Min allocation problem is also known as the textit{Fair Allocation problem}, or the textit{Santa Claus problem}. The Min-Max allocation problem is the problem of Scheduling on Unrelated Parallel Machines, and is also known as the $R , | , | C_{max}$ problem. In this paper, we are interested in instances of the problem that admit a Polynomial Time Approximation Scheme (PTAS). We show that an ordering property on the resources and the customers is important and paves the way for a PTAS. For the Max-Min allocation problem, we start with instances of the problem that can be viewed as a textit{convex bipartite graph}; a bipartite graph for which there exists an ordering of the resources such that each customer is interested in (has a positive evaluation for) a set of textit{consecutive} resources. We demonstrate a PTAS for the inclusion-free cases. This class of instances is equivalent to the class of bipartite permutation graphs. For the Min-Max allocation problem, we also obtain a PTAS for inclusion-free instances. These instances are not only of theoretical interest but also have practical applications.
Year
Venue
Field
2016
arXiv: Data Structures and Algorithms
Discrete mathematics,Combinatorics,Existential quantification,Bipartite permutation graphs,Scheduling (computing),Convex bipartite graph,Bipartite graph,Resource allocation,Polynomial-time approximation scheme,Mathematics
DocType
Volume
Citations 
Journal
abs/1610.00082
0
PageRank 
References 
Authors
0.34
2
4
Name
Order
Citations
PageRank
Kamyar Khodamoradi1163.68
Ramesh Krishnamurti224235.87
Arash Rafiey333928.08
Georgios Stamoulis4116.11