 Award ID(s):
 2022448
 NSFPAR ID:
 10341767
 Date Published:
 Journal Name:
 Operations research letters
 Volume:
 50
 Issue:
 2
 ISSN:
 01676377
 Page Range / eLocation ID:
 213217
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this

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

Random dimensionality reduction is a versatile tool for speeding up algorithms for highdimensional problems. We study its application to two clustering problems: the facility location problem, and the singlelinkage 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

We present a progressive approximation algorithm for the exact solution of several classes of interdiction games in which two noncooperative players (namely an attacker and a follower) interact sequentially. The follower must solve an optimization problem that has been previously perturbed by means of a series of attacking actions led by the attacker. These attacking actions aim at augmenting the cost of the decision variables of the followerโs optimization problem. The objective, from the attackerโs viewpoint, is that of choosing an attacking strategy that reduces as much as possible the quality of the optimal solution attainable by the follower. The progressive approximation mechanism consists of the iterative solution of an interdiction problem in which the attacker actions are restricted to a subset of the whole solution space and a pricing subproblem invoked with the objective of proving the optimality of the attacking strategy. This scheme is especially useful when the optimal solutions to the followerโs subproblem intersect with the decision space of the attacker only in a small number of decision variables. In such cases, the progressive approximation method can solve interdiction games otherwise intractable for classical methods. We illustrate the efficiency of our approach on the shortest path, 01 knapsack and facility location interdiction games. Summary of Contribution: In this article, we present a progressive approximation algorithm for the exact solution of several classes of interdiction games in which two noncooperative players (namely an attacker and a follower) interact sequentially. We exploit the discrete nature of this interdiction game to design an effective algorithmic framework that improves the performance of generalpurpose solvers. Our algorithm combines elements from mathematical programming and computer science, including a metaheuristic algorithm, a binary search procedure, a cuttingplanes algorithm, and supervalid inequalities. Although we illustrate our results on three specific problems (shortest path, 01 knapsack, and facility location), our algorithmic framework can be extended to a broader class of interdiction problems.more » « less

Abstract The
p โmedian problem (PMP) is one of the most applied location problems in urban and regional planning. As an NPโhard problem, the PMP remains challenging to solve optimally, especially for largeโsized problems. A number of heuristics have been developed to obtain PMP solutions in a fast manner. Among the heuristics, the Teitz and Bart (TB) algorithm has been found effective for finding highโquality solutions. In this article, we present a spatialโknowledgeโenhanced Teitz and Bart (STB) heuristic method for solving PMPs. The STB heuristic prioritizes candidate facility sites to be examined in the solution set based on the spatial distribution of demand and service provision. Tests based on a range of PMPs demonstrate the effectiveness of the STB heuristic. This new algorithm can be incorporated into current commercial GIS packages to solve a wide range of locationโallocation problems. 
Diversity is an important principle in data selection and summarization, facility location, and recommendation systems. Our work focuses on maximizing diversity in data selection, while offering fairness guarantees. In particular, we offer the first study that augments the MaxMin diversification objective with fairness constraints. More specifically, given a universe ๐ฐ of n elements that can be partitioned into m disjoint groups, we aim to retrieve a ksized subset that maximizes the pairwise minimum distance within the set (diversity) and contains a prespecified k_i number of elements from each group i (fairness). We show that this problem is NPcomplete even in metric spaces, and we propose three novel algorithms, linear in n, that provide strong theoretical approximation guarantees for different values of m and k. Finally, we extend our algorithms and analysis to the case where groups can be overlapping.more » « less