Fair k-Centers via Maximum Matching

associated with black people" (Sweeney, 2013) . The exis- The field of algorithms has seen a push for fair ness, or the removal of inherent bias, in recent history. In data summarization, where a much smaller subset of a data set is chosen to represent the whole of the data, fairness can be introduced by guaranteeing each "demographic group" a spe cific portion of the representative subset. Specifi cally, this paper examines this fair variant of the k-centers problem, where a subset of the data with cardinality k is chosen to minimize distance to the rest of the data. Previous papers working on this problem presented both a 3-approximation algo rithm with a super-linear runtime and a linear-time algorithm whose approximation factor is exponen tial in the number of demographic groups. This paper combines the best of each algorithm by pre senting a linear-time algorithm with a guaranteed 3-approximation factor and provides empirical evidence of both the algorithm's runtime and ef fectiveness.