Maximizing coverage while ensuring fairness: a tale of conflicting objective
| Autor: | Asudeh, Abolfazl, Berger-Wolf, Tanya, DasGupta, Bhaskar, Sidiropoulos, Anastasios |
|---|---|
| Rok vydání: | 2020 |
| Předmět: | |
| Zdroj: | Algorithmica, 85, 1287-1331, 2023 |
| Druh dokumentu: | Working Paper |
| DOI: | 10.1007/s00453-022-01072-1 |
| Popis: | Ensuring fairness in computational problems has emerged as a $key$ topic during recent years, buoyed by considerations for equitable resource distributions and social justice. It $is$ possible to incorporate fairness in computational problems from several perspectives, such as using optimization, game-theoretic or machine learning frameworks. In this paper we address the problem of incorporation of fairness from a $combinatorial$ $optimization$ perspective. We formulate a combinatorial optimization framework, suitable for analysis by researchers in approximation algorithms and related areas, that incorporates fairness in maximum coverage problems as an interplay between $two$ conflicting objectives. Fairness is imposed in coverage by using coloring constraints that $minimizes$ the discrepancies between number of elements of different colors covered by selected sets; this is in contrast to the usual discrepancy minimization problems studied extensively in the literature where (usually two) colors are $not$ given $a$ $priori$ but need to be selected to minimize the maximum color discrepancy of $each$ individual set. Our main results are a set of randomized and deterministic approximation algorithms that attempts to $simultaneously$ approximate both fairness and coverage in this framework. Comment: Revised version, under submission to journal |
| Databáze: | arXiv |
| Externí odkaz: |
|