@inproceedings{750bd9b4fab14b4193c0bd6a6d6c9f62,
title = "Brief Announcement: Towards Proportionate Fair Assignment",
abstract = "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.",
keywords = "Approximation algorithms, Assignment, Cloud system, Perfect matching, Proportionate fairness",
author = "Baruch Schieber",
note = "Publisher Copyright: {\textcopyright} The Author(s), under exclusive license to Springer Nature Switzerland AG 2025.; 26th International Symposium on Stabilization, Safety, and Security of Distributed Systems, SSS 2024 ; Conference date: 20-10-2024 Through 22-10-2024",
year = "2025",
doi = "10.1007/978-3-031-74498-3_18",
language = "English (US)",
isbn = "9783031744976",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Science and Business Media Deutschland GmbH",
pages = "255--259",
editor = "Toshimitsu Masuzawa and Yoshiaki Katayama and Yonghwan Kim and Hirotsugu Kakugawa and Junya Nakamura",
booktitle = "Stabilization, Safety, and Security of Distributed Systems - 26th International Symposium, SSS 2024, Proceedings",
address = "Germany",
}