دانلود مقاله انگلیسی رایگان:تخصیص عادلانه Max-min برای منابع با تقسیمات ترکیبی - 2019
بلافاصله پس از پرداخت دانلود کنید
دانلود مقاله انگلیسی سیستم های خبره رایگان
  • Max-min fair allocation for resources with hybrid divisibilities Max-min fair allocation for resources with hybrid divisibilities
    Max-min fair allocation for resources with hybrid divisibilities

    سال انتشار:

    2019


    عنوان انگلیسی مقاله:

    Max-min fair allocation for resources with hybrid divisibilities


    ترجمه فارسی عنوان مقاله:

    تخصیص عادلانه Max-min برای منابع با تقسیمات ترکیبی


    منبع:

    Sciencedirect - Elsevier - Expert Systems With Applications, 124 (2019) 325-340: doi:10:1016/j:eswa:2019:01:071


    نویسنده:

    Yunpeng Li a , c , Changjie He b , Yichuan Jiang a , ∗, Weiwei Wu a , Jiuchuan Jiang d , Wei Zhang e , Hui Fan f


    چکیده انگلیسی:

    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 divis- ible 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 re- sources 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 in- vestigate 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 √ 10 + ε ( ε > 0)-factor approxima- tion algorithm for the restricted case where u ij ∈ {0, u j } (i.e., the utility of a resource j is either 0 or u j for each agent i ) and the agent valuations for the divisible resources are in proximity to each other. More- over, 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.
    Keywords: Max-min fair allocation | Indivisible resources | Divisible resources | Multi-agent systems


    سطح: متوسط
    تعداد صفحات فایل pdf انگلیسی: 16
    حجم فایل: 879 کیلوبایت

    قیمت: رایگان


    توضیحات اضافی:




اگر این مقاله را پسندیدید آن را در شبکه های اجتماعی به اشتراک بگذارید (برای به اشتراک گذاری بر روی ایکن های زیر کلیک کنید)

تعداد نظرات : 0

الزامی
الزامی
الزامی
rss مقالات ترجمه شده rss مقالات انگلیسی rss کتاب های انگلیسی rss مقالات آموزشی