Research On The Problem Of Minmax Fair Sharing For Resource

In this thesis,we study the problem of the fair sharing for weighted resources,which is the generalization of the semi-matching.In most data center schedulers,there are many computers and users.Because of hard placement constrains,some computers'resources only can be used by partial users.The first problem is how to seek min-max fair sharing for resources.The problems are described as follows:Given a bipartite graph G=?U?V,E;c?with U as the set of computer,and V as the set of user.The edge of each?u_j,v_i??E is that the u_j of computers'CPU can be distributed to v_i of user.c:E?N₊ is the function of capacity.The first problem is to seek a quasi-matching f that min z?f?=max?i?V???j:i?N_j? f_ji;On the basis of studying the problem,we can generalize the second problem that is how to seek max-min fair sharing for resources.The second problem is to seek a quasi-matching f that max z?f?=min?i?V???j:i?N_j ?f_ji.We designed two optimal algorithms called as BS and RCRP for the first prob-lem,whose time complexity are O?n³?and O?n₁m₁²m?respectively,where n₁,m₁,n,m denote the number of computer,user,the sum of computer and user,the number of edge.We designed one lexicographically order optimal algorithm called as PF for the second problem.