The price of envy-freeness in machine scheduling

详细信息    查看全文

• 作者：Vittorio Bilò ; ^a ; ^{vittorio.bilo@unisalento.it" class="auth_mail" title="E-mail the corresponding author} ; Angelo Fanelli^b ; ^{angelo.fanelli@unicaen.fr" class="auth_mail" title="E-mail the corresponding author} ; Michele Flammini^c ; ^d ; ^{michele.flammini@univaq.it" class="auth_mail" title="E-mail the corresponding author} ; Gianpiero Monaco^c ; ^{gianpiero.monaco@univaq.it" class="auth_mail" title="E-mail the corresponding author} ; Luca Moscardelli^e ; ^{luca.moscardelli@unich.it" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Envy-freeness ; Machine scheduling
• 刊名：Theoretical Computer Science
• 出版年：2016
• 出版时间：1 February 2016
• 年：2016
• 卷：613
• 期：Complete
• 页码：65-78
• 全文大小：432 K

文摘

We consider k-envy-free assignments for scheduling problems in which the completion time of each machine is not k   times larger than the one she could achieve by getting the jobs of another machine, for a given factor class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0304397515011123&_mathId=si1.gif&_user=111111111&_pii=S0304397515011123&_rdoc=1&_issn=03043975&md5=832540adcb2e9a14dd71dcb0488c7fde" title="Click to view the MathML source">k≥1class="mathContainer hidden">class="mathCode">$k\ge 1$. We introduce and investigate the notion of price of k-envy-freeness, defined as the ratio between the makespan of the best k-envy-free assignment and that of an optimal allocation achievable without envy-freeness constraints. We provide exact or asymptotically tight bounds on the price of k-envy-freeness for all the basic scheduling models, that is unrelated, related and identical machines. Moreover, we show how to efficiently compute such allocations with a worsening multiplicative factor being at most the best approximation ratio for the minimum makespan problem guaranteed by a polynomial time algorithm for each specific model. Finally, we extend our results to the case of restricted assignments and to the objective of minimizing the sum of the completion times of all the machines.