Fairness in Resource Allocation and Slowed-down Dependent Rounding

Autor:	Harris, David G., Pensyl, Thomas, Srinivasan, Aravind, Trinh, Khoa
Rok vydání:	2017
Předmět:	Computer Science - Data Structures and Algorithms Computer Science - Discrete Mathematics
Druh dokumentu:	Working Paper
Popis:	We consider an issue of much current concern: could fairness, an issue that is already difficult to guarantee, worsen when algorithms run much of our lives? We consider this in the context of resource-allocation problems, we show that algorithms can guarantee certain types of fairness in a verifiable way. Our conceptual contribution is a simple approach to fairness in this context, which only requires that all users trust some public lottery. Our technical contributions are in ways to address the $k$-center and knapsack-center problems that arise in this context: we develop a novel dependent-rounding technique that, via the new ingredients of "slowing down" and additional randomization, guarantees stronger correlation properties than known before. Comment: We decided to split these results to two separate papers. Please see arXiv:1709.06995
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/1704.06528 Zobrazit plný text záznamu View this record from Arxiv