The well known assignment problem finds an optimal assignment of tasks to agents. Optimal assignment is applicable to the placement of virtual machines in cloud systems to optimize resource allocation and ensure efficient operation. It is also applicable to fault-tolerant computation to ensure continued operation in case of component failures. In some instances the assignment needs to satisfy extraneous fairness constraints. For example, in a multi-tenant cloud environment the assignment has to guarantee equitable treatment of customers. We initiate the study of proportionate fair assignment. In the multi-tenant setting such an assignment ensures proportionate representation of the customers over all servers. We show that even the simple case of computing an assignment that ensures equal representation of two customers is hard. On the positive side, we present a 1/2-approximation algorithm for computing an assignment that ensures equal representation of two customers.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Brief Announcement: Towards Proportionate Fair Assignment

  • Baruch Schieber

摘要

The well known assignment problem finds an optimal assignment of tasks to agents. Optimal assignment is applicable to the placement of virtual machines in cloud systems to optimize resource allocation and ensure efficient operation. It is also applicable to fault-tolerant computation to ensure continued operation in case of component failures. In some instances the assignment needs to satisfy extraneous fairness constraints. For example, in a multi-tenant cloud environment the assignment has to guarantee equitable treatment of customers. We initiate the study of proportionate fair assignment. In the multi-tenant setting such an assignment ensures proportionate representation of the customers over all servers. We show that even the simple case of computing an assignment that ensures equal representation of two customers is hard. On the positive side, we present a 1/2-approximation algorithm for computing an assignment that ensures equal representation of two customers.