Please use this identifier to cite or link to this item:
Full metadata record
DC FieldValueLanguage
dc.contributor.authorLi, Yunpengen_US
dc.contributor.authorHe, Changjieen_US
dc.contributor.authorJiang, Yichuanen_US
dc.contributor.authorWu, Weiweien_US
dc.contributor.authorJiang, Jiuchuanen_US
dc.contributor.authorZhang, Weien_US
dc.contributor.authorFan, Huien_US
dc.identifier.citationLi, Y., He, C., Jiang, Y., Wu, W., Jiang, J., Zhang, W. & Fan, H. (2019). Max-min fair allocation for resources with hybrid divisibilities. Expert Systems With Applications, 124, 325-340.
dc.description.abstractResource allocation is a classic problem in economics and computer science. The application scenarios of resource allocation include inheritance settlements, computation resource sharing and so on. This paper focuses on the max-min fair allocation of resources in which m resources need to be allocated to n agents while maximizing the minimum utility of any agent. When money transfer is not allowed, the existing work on max-min fair allocation only focuses on the fair allocation of indivisible resources. However, in real applications, the allocated resource set may simultaneously include indivisible resources and divisible resources, e.g., the allocated resources in distributed systems include the indivisible CPU resources, the divisible storage resource and the divisible bandwidth resource. The combination of indivisible resources and divisible resources creates a new challenge and requires us to consider how to coordinate the allocations of indivisible resources and divisible resources in the allocation process. Therefore, we investigate the combined max-min fair allocation problem in which the allocated resource set consists of both indivisible resources and divisible resources. We present a 6+2 (ε > 0)-factor approximation algorithm for the restricted case where uij ∈ {0, uj} (i.e., the utility of a resource j is either 0 or uj for each agent i) and the agent valuations for the divisible resources are in proximity to each other. Moreover, we propose an approximation algorithm for the general case based on the augmented flow idea. Experiments conducted on real data show that the average performance of the proposed approximation algorithm is better than 80% of the performance of the optimal algorithm, which requires exponential time in the worst case unless P = NP. To the best of our knowledge, the proposed algorithm is the first approximation algorithm for the general case of the combined max-min fair allocation problem when money transfer is not allowed. The proposed algorithm can be adopted to design more efficient expert systems that apply to resource allocation in distributed systems, inheritance settlements and so on. The adoption of the proposed algorithm contributes to promoting the broader application of expert systems in the fair allocation of computation resources and social resources. The experimental results show that the proposed algorithm can perform well in real applications.en_US
dc.relation.ispartofExpert Systems with Applicationsen_US
dc.rights© 2019 Elsevier Ltd. All rights reserved.en_US
dc.subjectEngineering::Computer science and engineeringen_US
dc.titleMax-min fair allocation for resources with hybrid divisibilitiesen_US
dc.typeJournal Articleen
dc.contributor.schoolSchool of Computer Science and Engineeringen_US
dc.subject.keywordsMax-min Fair Allocationen_US
dc.subject.keywordsIndivisible Resourcesen_US
dc.description.acknowledgementThe work was supported in part by the National Natural Science Foundation of China (61472079, 61170164, 61806053, 61807008), and the Natural Science Foundation of Jiangsu Province of China (BK20171363, BK20180356, BK20180369).en_US
item.fulltextNo Fulltext-
Appears in Collections:SCSE Journal Articles

Page view(s)

Updated on May 20, 2022

Google ScholarTM




Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.