我们研究了度量设施选址问题中的客户不兼容约束，即每个设施所服务的客户集合必须是给定 matroid (\mathcal M) 的独立集。首先考虑所有设施开设费用相同且仅存在单一 matroid (\mathcal M) 的情形。我们设计了一种基于 add、delete、single‑swap 操作的多换局部搜索算法，在多项式时间内实现了 ((1+\sqrt{2}+\epsilon)) 的近似比。
在设施开设费用不均且 (\mathcal M) 为分割 matroid 的情况下，限制每个分组 (g) 最多有 (b_g) 位客户被分配到同一设施。针对该设置，我们得到了一种 ((15+\epsilon)) 近似的多项式时间算法。
技术核心在于：连接成本可以利用最小连接成本函数的超模性直接界定；而设施开设成本的分析则需要全新的 压缩论证。我们基于 matroid 交换原理，识别出一组局部打开的设施，其数量不超过最优设施集合的规模。对这组之外的设施，仍可使用超模性得到上界；对剩余设施则采用不同的论证手段完成费用界定。
进一步，我们考察了每个潜在设施 (i) 拥有各自 matroid (\mathcal M_i) 的更一般模型，并证明即使所有 (\mathcal M_i) 均为相同分割 matroid（仅组上限 (b_g) 不同），问题的近似难度仍至少与集合覆盖等价，难以获得更好近似。
这些结果表明，在统一容量且带有客户独立性约束的设施选址问题上，局部搜索技术可以通过创新的压缩论证得到有效推广，并在更广泛的分割 matroid 与异常点模型中保持可观的近似比。
点评：本文通过创新的压缩论证将局部搜索的分析从普通 CFL 推广到带 matroid 约束的情形，取得了可观的近似比，并揭示了问题的固有难度，为后续研究提供了有价值的思路。