Georgia Institute of Technology College of Sciences

The classic facility location problem seeks to open a set of facilities to minimize the cost of opening the chosen facilities and the total cost of connecting all the clients to their nearby open facilities. Such an objective may induce an unequal cost over certain socioeconomic groups of clients (i.e., total distance traveled by clients in such a group). This is important when planning the location of socially relevant facilities such as emergency rooms and grocery stores. In this work, we consider a fair version of the problem by minimizing the L_p-norm of the total distance traveled by clients across different socioeconomic groups and the cost of opening facilities, to penalize high access costs to open facilities across r groups of clients. This generalizes classic facility location (p = 1) and the minimization of the maximum total distance traveled by clients in any group (p = infinity). However, it is often unclear how to select a specific "p" to model the cost of unfairness. To get around this, we show the existence of a small portfolio of at most (log2r + 1) solutions for r (disjoint) client groups, where for any L_p-norm, at least one of the solutions is a constant-factor approximation with respect to any L_p-norm. We also show that such a dependence on r is necessary by showing the existence of instances where at least ~ sqrt(log2r) solutions are required in such a portfolio. Moreover, we give efficient algorithms to find such a portfolio of solutions. Additionally, We introduce the notion of refinement across the solutions in the portfolio. This property ensures that once a facility is closed in one of the solutions, all clients assigned to it are reassigned to a single facility and not split across open facilities. We give poly(exp(sqrt(r))-approximation for refinement in general metrics and O(log r)-approximation for the line and tree metrics. This is joint work with Swati Gupta and Mohit Singh.