부산대학교 도서관

Summary: ``We consider $k$-envy-free assignments for schedulingproblems in which the completion time of each machine is not $k$ timeslarger than the one she could achieve by getting the jobs of anothermachine, for a given factor $k\geq1$. We introduce and investigate thenotion of price of $k$-envy-freeness, defined as the ratio between themakespan of the best $k$-envy-free assignment and that of an optimalallocation achievable without envy-freeness constraints. We provideexact or asymptotically tight bounds on the price of $k$-envy-freenessfor all the basic scheduling models, that is unrelated, related andidentical machines. Moreover, we show how to efficiently compute suchallocations with a worsening multiplicative factor being at most thebest approximation ratio for the minimum makespan problem guaranteed bya polynomial time algorithm for each specific model. Finally, we extendour results to the case of restricted assignments and to the objectiveof minimizing the sum of the completion times of all the machines.''