arXiv preprint ·
Facility Location with Customer Incompatibilities
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
We study metric facility location with customer incompatibilities, where the clients assigned to each facility must satisfy prescribed independence constraints. We first consider the setting of facility-opening costs and where there is a single matroid $\mathcal M$ over the clients and the set of clients assigned to an open facility must be an independent set in $\mathcal M$. We develop a polynomial-time \((1+\sqrt{2}+ε)\)-approximation algorithm for this setting. We further obtain a polynomial-time \((15+ε)\)-approximation algorithm for the case of non-uniform facility-opening costs when $\mathcal M$ is a partition matroid that only permits $b_g$ clients to be assigned to a facility for each group $g$ in the partition. Both settings are substantial generalizations of Capacitated Facility Location with uniform capacities. Our algorithms are based on local search using add, delete, and single-swap operations. As with CFL, bounding the connection cost is reasonably straightforward using supermodularity of the minimum connection-cost function. However, bounding the facility opening costs requires novel arguments in both cases. We use a ``compression'' argument based on matroid exchange principles to identify a subset of the locally opened facilities whose size is no larger than that of an optimal facility set. The opening costs of facilities outside this subset can be bounded using supermodularity, while bounding the costs of the remaining facilities requires different arguments. It is natural to consider a variant where each possible facility $i$ has its own matroid $\mathcal M_i$ defining the subsets of clients it can feasibly serve. We also show problem is at least as hard to approximate as Set Cover even if all $\mathcal M_i$ are partition matroids that have the same partition of clients, just different group bounds $b_g$.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Limits and Constants of OpenAI's Claimed ETH Refutation
An $\mathsf{FPRAS}$ for Mixed Volumes
Sharper Bounds for Graphical Two-Choice Allocation
Compressed Oracle Duality: A simple framework for knowing what quantum adversaries know
Three-phase time minimization transportation problem with non-idle phases: a polynomial two-witness algorithm
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.