@booklet {edithcohen-ema2010,
	title = {Envy-Free Makespan Approximation},
	howpublished = {Discussion Papers},
	year = {2010},
	month = {2},
	abstract = {We study envy-free mechanisms for scheduling tasks on unrelated machines (agents) that approximately minimize the makespan. For indivisible tasks, we put forward an envy-free poly-time mechanism that approximates the minimal makespan to within a factor of O(logm), where m is the number of machines. We also show a lower bound of Omega(log m/log logm). This improves the recent result of Mu{\textquoteright}alem [22] who give an upper bound of (m + 1)/2, and a lower bound of 2 - 1/m. For divisible tasks, we show that there always exists an envy-free poly-time mechanism with optimal makespan. Finally, we demonstrate how our mechanism for envy free makespan minimization can be interpreted as a market clearing problem.},
	url = {/files/dp539.pdf},
	author = {Edith Cohen, Michal Feldman, Amos Fiat, Haim Kaplan and Svetlana Olonetsky}
}
