More Like this

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

   https://doi.org/10.1145/3580507.3597664  

   Gupta, Swati; Moondra, Jai; Singh, Mohit (July 2023, EC '23: Proceedings of the 24th ACM Conference on Economics and Computation)

   Given a set of facilities and clients, and costs to open facilities, the classic facility location problem seeks to open a set of facilities and assign each client to one open facility to minimize the cost of opening the chosen facilities and the total distance of the clients to their assigned 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. In this work, we consider a fair version of the problem where we are given 𝑟 clients groups that partition the set of clients, and the distance of a given group is defined as the average distance of clients in the group to their respective open facilities. The objective is to minimize the Minkowski 𝑝-norm of vector of group distances, to penalize high access costs to open facilities across 𝑟 groups of clients. This generalizes classic facility location (𝑝 = 1) and the minimization of the maximum group distance (𝑝 = ∞). However, in practice, fairness criteria may not be explicit or even known to a decision maker, and it is often unclear how to select a specific "𝑝" to model the cost of unfairness. To get around this, we study the notion of solution portfolios where for a fixed problem instance, we seek a small portfolio of solutions such that for any Minkowski norm 𝑝, one of these solutions is an 𝑂(1)-approximation. Using the geometric relationship between various 𝑝-norms, we show the existence of a portfolio of cardinality 𝑂(log 𝑟), and a lower bound of (\sqrt{log r}). There may not be common structure across different solutions in this portfolio, which can make planning difficult if the notion of fairness changes over time or if the budget to open facilities is disbursed over time. For example, small changes in 𝑝 could lead to a completely different set of open facilities in the portfolio. Inspired by this, we introduce the notion of refinement, which is a family of solutions for each 𝑝-norm satisfying a combinatorial property. This property requires that (1) the set of facilities open for a higher 𝑝-norm must be a subset of the facilities open for a lower 𝑝-norm, and (2) all clients assigned to an open facility for a lower 𝑝-norm must be assigned to the same open facility for any higher 𝑝-norm. A refinement is 𝛼-approximate if the solution for each 𝑝-norm problem is an 𝛼-approximation for it. We show that it is sufficient to consider only 𝑂(log 𝑟) norms instead of all 𝑝-norms, 𝑝 ∈ [1, ∞] to construct refinements. A natural greedy algorithm for the problem gives a poly(𝑟)-approximate refinement, which we improve to poly(r^1/\sqrt{log 𝑟})-approximate using a recursive algorithm. We improve this ratio to 𝑂(log 𝑟) for the special case of tree metric for uniform facility open cost. Our recursive algorithm extends to other settings, including to a hierarchical facility location problem that models facility location problems at several levels, such as public works departments and schools. A full version of this paper can be found at https://arxiv.org/abs/2211.14873. 

   more » « less
2. Randomized Strategic Facility Location with Predictions

   Balkanski, Eric; Gkatzelis, Vasilis; Shahkarami, Golnoosh (December 2024, Advances in Neural Information Processing Systems 37 (NeurIPS 2024))

   Globerson, A; Mackey, L; Belgrave, D; Fan, A; Paquet, U; Tomczak, J; Zhang, C (Ed.)

   In the strategic facility location problem, a set of agents report their locations in a metric space and the goal is to use these reports to open a new facility, minimizing an aggregate distance measure from the agents to the facility. However, agents are strategic and may misreport their locations to influence the facility’s placement in their favor. The aim is to design truthful mechanisms, ensuring agents cannot gain by misreporting. This problem was recently revisited through the learning-augmented framework, aiming to move beyond worst-case analysis and design truthful mechanisms that are augmented with (machine-learned) predictions. The focus of this prior work was on mechanisms that are deterministic and augmented with a prediction regarding the optimal facility location. In this paper, we provide a deeper understanding of this problem by exploring the power of randomization as well as the impact of different types of predictions on the performance of truthful learning-augmented mechanisms. We study both the single-dimensional and the Euclidean case and provide upper and lower bounds regarding the achievable approximation of the optimal egalitarian social cost. 

   more » « less
3. Randomized Dimensionality Reduction for Facility Location and Single-Linkage Clustering

   Narayanan, S; Silwal, S; Indyk, P; Zamir, O (January 2021, International Conference on Machine Learning)

   Random dimensionality reduction is a versatile tool for speeding up algorithms for high-dimensional problems. We study its application to two clustering problems: the facility location problem, and the single-linkage hierarchical clustering problem, which is equivalent to computing the minimum spanning tree. We show that if we project the input pointset 𝑋 onto a random 𝑑=𝑂(𝑑𝑋)-dimensional subspace (where 𝑑𝑋 is the doubling dimension of 𝑋), then the optimum facility location cost in the projected space approximates the original cost up to a constant factor. We show an analogous statement for minimum spanning tree, but with the dimension 𝑑 having an extra loglog𝑛 term and the approximation factor being arbitrarily close to 1. Furthermore, we extend these results to approximating solutions instead of just their costs. Lastly, we provide experimental results to validate the quality of solutions and the speedup due to the dimensionality reduction. Unlike several previous papers studying this approach in the context of 𝑘-means and 𝑘-medians, our dimension bound does not depend on the number of clusters but only on the intrinsic dimensionality of 𝑋. 

   more » « less
4. Balancing Notions of Equity: Trade-offs Between Fair Portfolio Sizes and Achievable Guarantees

   https://doi.org/10.1137/1.9781611978322.33  

   Gupta, Swati; Moondra, Jai; Singh, Mohit (January 2025, Society for Industrial and Applied Mathematics)

   Motivated by fairness concerns, we study existence and computation of portfolios, defined as: given anoptimization problem with feasible solutions D, a class C of fairness objective functions, a set X of feasible solutions is an α-approximate portfolio if for each objective f in C, there is an α-approximation for f in X. We study the trade-off between the size |X| of the portfolio and its approximation factor αfor various combinatorial problems, such as scheduling, covering, and facility location, and choices of C as top-k, ordered and symmetric monotonic norms. Our results include: (i) an α-approximate portfolio of size O(log d*log(α/4))for ordered norms and lower bounds of size \Omega( log dlog α+log log d)for the problem of scheduling identical jobs on d unidentical machines, (ii) O(log n)-approximate O(log n)-sized portfolios for facility location on n points for symmetric monotonic norms, and (iii) logO(d)^(r^2)-size O(1)-approximate portfolios for ordered norms and O(log d)-approximate for symmetric monotonic norms for covering polyhedra with a constant rnumber of constraints. The latter result uses our novel OrderAndCount framework that obtains an exponentialimprovement in portfolio sizes compared to current state-of-the-art, which may be of independent interest. 

   more » « less
5. Facility Location Games with Optional Preferences: A Revisit

   https://doi.org/10.1609/aaai.v39i13.33542  

   Sha, Xingchen; Bao, Shuyu; Chan, Hau; Chau, Vincent; Fong, Ken_C K; Li, Minming (April 2025, Proceedings of the AAAI Conference on Artificial Intelligence)

   We study the k-facility location games with optional preferences on the line. In the games, each strategic agent has a public location preference on the k facility locations and a private optional preference on the preferred/acceptable set of facilities out of the k facilities. Our goal is to design strategyproof mechanisms to elicit agents’ optional preferences and locate k facilities to minimize the social or maximum cost of agents based on their facility preferences and public agent locations. We consider two variants of the facility location games with optional preferences: the Min variant and the Max variant where the agent’s cost is defined as their distance to the closest acceptable facility and the farthest acceptable facility, respectively. For the Min variant, we present two deterministic strategyproof mechanisms to minimize the maximum cost and social cost with k ≥ 3 facilities, achieving approximation ratios of 3 and 2n+1 respectively. We complement the results by establishing lower bounds of 3/2 and n/4 for the approximation ratios achievable by any deterministic strategyproof mechanisms for the maximum cost and social cost, respectively. We then improve our results in a special setting of the Min variant where there are exactly three facilities and present two deterministic strategyproof mechanisms to minimize the maximum cost and social cost. For the Max variant, we present an optimal deterministic strategyproof mechanism for the maximum cost and a k-approximation deterministic strategyproof mechanism for the social cost. 

   more » « less