Which Lp norm is the fairest? Approximations for fair facility location across all "p"

Fair facility location problems try to balance access costs to open facilities borne by different groups of people by minimizing the Lp norm of these group distances. However, there is no clear choice of "p" in the current literature. We present a novel approach to address the challenge of choosing the right notion of fairness. We introduce the concept of portfolios, a set of solutions that contains an approximately optimal solution for each objective in a given class of objectives, such as Lp norms. This concept opens up new possibilities for getting around the "right" notion of fairness for many problems. For r client groups, we demonstrate portfolios of size Theta(log r) for the facility location and k-clustering problems, with an O(1)-approximate solution for each Lp norm. Further, motivated by the Justice40 Initiative that provides rolling budget investments, we impose a refinement-like structure on the portfolio. We develop novel approximation algorithms for these structured portfolios and show experimental evidence of their performance in two US counties. We also present a planning tool that provides potential ways to expand access to US healthcare facilities, which might be of independent interest to policymakers.