Please use this identifier to cite or link to this item: https://hdl.handle.net/10356/152122
Title: Max-min fair allocation for resources with hybrid divisibilities
Authors: Li, Yunpeng
He, Changjie
Jiang, Yichuan
Wu, Weiwei
Jiang, Jiuchuan
Zhang, Wei
Fan, Hui
Keywords: Engineering::Computer science and engineering
Issue Date: 2019
Source: Li, 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. https://dx.doi.org/10.1016/j.eswa.2019.01.071
Journal: Expert Systems with Applications
Abstract: Resource 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.
URI: https://hdl.handle.net/10356/152122
ISSN: 0957-4174
DOI: 10.1016/j.eswa.2019.01.071
Rights: © 2019 Elsevier Ltd. All rights reserved.
Fulltext Permission: none
Fulltext Availability: No Fulltext
Appears in Collections:SCSE Journal Articles

Page view(s)

112
Updated on May 20, 2022

Google ScholarTM

Check

Altmetric


Plumx

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