We investigate metric facility location with customer incompatibility constraints, where the set of clients assigned to each facility must form an independent set of a given matroid (\mathcal M). In the first setting all facilities have the same opening cost and there is a single matroid (\mathcal M). By employing a local‑search framework that uses add, delete, and single‑swap operations, we obtain a polynomial‑time ((1+\sqrt{2}+\epsilon))‑approximation algorithm.
When facility opening costs are non‑uniform and (\mathcal M) is a partition matroid that limits each group (g) to at most (b_g) clients per facility, we design a polynomial‑time algorithm with approximation ratio ((15+\epsilon)).
The main technical challenge lies in bounding the opening costs. While the connection cost follows from the supermodularity of the minimum‑connection‑cost function, the opening cost analysis requires a novel compression argument. Using matroid exchange principles we identify a subset of locally opened facilities whose cardinality does not exceed that of an optimal facility set. The opening costs of facilities outside this subset are bounded via supermodularity; the remaining facilities are handled with a different argument.
We also consider a more general variant where each potential facility (i) has its own matroid (\mathcal M_i). We prove that even when all (\mathcal M_i) are identical partition matroids (only the group bounds (b_g) differ), the problem is at least as hard to approximate as Set Cover, implying strong hardness.
These results demonstrate that local‑search techniques, enhanced by the compression argument, can be effectively extended to capacitated facility location with matroid‑based client independence constraints, achieving meaningful approximation guarantees even under non‑uniform opening costs and outlier extensions.
Review: The paper introduces a clever compression technique that lifts local‑search analysis from classic CFL to matroid‑constrained settings, achieving solid approximation ratios while also establishing inherent hardness, thus offering valuable directions for future work.