Dynamic Weighted Fairness with Minimal Disruptions
Dynamic Weighted Fairness with Minimal Disruptions
复制标题
动态加权公平，干扰最小
DOI：
10.1145/3379485
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Pruhs, Kirk
中科院分区：
文献类型：
--
作者：
Im, Sungjin;Moseley, Benjamin;Munagala, Kamesh;Pruhs, Kirk
在本文中，我们考虑以下动态公平分配问题：给定一系列作业到达和离开的序列，目标是根据目标公平分配策略维持资源的近似公平分配，同时最小化中断总数，即任何作业分配更改的次数。我们考虑了一系列丰富的公平分配政策，这些政策显着概括了之前工作中考虑的政策。我们首先考虑工作仅到达或工作仅离开的模型。我们对每个时间步保持恒定的近似公平分配所需的中断数量提出了严格的上限和下限。特别是，对于工作具有权重且资源分配与工作权重成正比的典型情况，我们表明，维持恒定的近似公平分配需要每个工作 θ(łog^* n) 次中断，几乎与单位权重情况下先前工作的界限相匹配。对于更一般的设置，即分配政策仅在新工作到来时减少对工作的分配，我们表明维持恒定的近似公平分配需要每个工作的 θ(łog n) 中断。然后我们考虑工作可以到达和离开的模型。我们首先展示了维持任意实例的恒定近似公平性所需的中断数量的强下限。相比之下，我们随后表明，如果作业的权重与作业到达和离开的顺序无关，则存在一种算法可以在每个作业的预期中断情况下保持恒定的近似公平性。最后，我们展示了如何将我们的结果扩展到具有多种资源的设置。
In this paper, we consider the following dynamic fair allocation problem: Given a sequence of job arrivals and departures, the goal is to maintain an approximately fair allocation of the resource against a target fair allocation policy, while minimizing the total number of \em disruptions, which is the number of times the allocation of any job is changed. We consider a rich class of fair allocation policies that significantly generalize those considered in previous work. We first consider the models where jobs only arrive, or jobs only depart. We present tight upper and lower bounds for the number of disruptions required to maintain a constant approximate fair allocation every time step. In particular, for the canonical case where jobs have weights and the resource allocation is proportional to the job's weight, we show that maintaining a constant approximate fair allocation requires Θ(łog^* n) disruptions per job, almost matching the bounds in prior work for the unit weight case. For the more general setting where the allocation policy only decreases the allocation to a job when new jobs arrive, we show that maintaining a constant approximate fair allocation requires Θ(łog n) disruptions per job. We then consider the model where jobs can both arrive and depart. We first show strong lower bounds on the number of disruptions required to maintain constant approximate fairness for arbitrary instances. In contrast we then show that there there is an algorithm that can maintain constant approximate fairness withexpected disruptions per job if the weights of the jobs are independent of the jobs arrival and departure order. We finally show how our results can be extended to the setting with multiple resources.
DOI：
10.1145/3219166.3219179
发表时间：
2018-06
期刊：
Proceedings of the 2018 ACM Conference on Economics and Computation
影响因子：
--
作者：
Gerdus Benade;Aleksandr M. Kazachkov;Ariel D. Procaccia;Alexandros Psomas
通讯作者：
Gerdus Benade;Aleksandr M. Kazachkov;Ariel D. Procaccia;Alexandros Psomas
一般估值的动态公平分配问题
DOI：
10.24963/ijcai.2018/52
发表时间：
2018
期刊：
Proceedings of the forty-sixth annual ACM symposium on Theory of computing
影响因子：
--
作者：
Bo Li;Yingkai Li
通讯作者：
Yingkai Li
受控动态公平划分
DOI：
10.1145/3033274.3085123
发表时间：
2017
期刊：
Proceedings of the 2017 ACM Conference on Economics and Computation
影响因子：
--
作者：
E. Friedman;Alexandros Psomas;Shai Vardi
通讯作者：
Shai Vardi