Envy-free makespan approximation: extended abstract
Lists
Only you see this
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(log m), where m is the number of machines. We also show a lower bound of γ(log m / log log m). This improves the recent result of Mu'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.
BibTeX
@inproceedings{cohen2010envy,
author = {Edith Cohen and Michal Feldman and Amos Fiat and Haim Kaplan and Svetlana Olonetsky},
title = {{Envy-free makespan approximation: extended abstract}},
booktitle = {EC},
year = {2010},
url = {https://openreview.net/forum?id=26h1o90ud2w},
}