2026-07-20T14:36:12Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:4393 2024-03-06T10:35:00Z ddc:004 open_access

PTAS for Ordered Instances of Resource Allocation Problems Khodamoradi, Kamyar Krishnamurti, Ramesh Rafiey, Arash Stamoulis, Georgios Approximation Algorithms Convex Bipartite Graphs Resource Allocation 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). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Kamyar Khodamoradi and Ramesh Krishnamurti and Arash Rafiey and Georgios Stamoulis 2013 Is Part Of LIPIcs, Volume 24, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2013.461 urn:nbn:de:0030-drops-43936 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2013.461 eng https://creativecommons.org/licenses/by/3.0/legalcode