2012/05/08 by Amos Fiat, Fiat, Amos, Ariel Levavi +1
Computer Science · Decision Sciences · #Auction Theory and Applications #Complexity and Algorithms in Graphs #Computer Science and Game Theory (cs.GT) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Optimization and Search Problems #cs.DM #cs.GT
paper · pdf · doi:10.48550/arxiv.1205.1786
arxiv created 2012/05/08 · openalex publication_date 2012/05/08 · arxiv updated 2012/05/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this work we give a tight lower bound on makespan approximations for envy-free allocation mechanism dedicated to scheduling tasks on unrelated machines. Specifically, we show that no mechanism exists that can guarantee an envy-free allocation of jobs to m machines with a makespan of less than a factor of O(log m) of the minimal makespan. Combined with previous results, this paper definitively proves that the optimal algorithm for obtaining a minimal makespan for any envy-free division can at best approximate the makespan to a factor of O(log m).