定义
输入：二分图 \(G\)，顶点集分为设施集 \(F\) 和客户集 \(D\)。设施 \(i\) 的开放费用为 \(f_i\)，用户 \(j\) 到设施 \(i\) 的有权为 \(c_{ij}\) 的边代表距离。边权满足三角不等式。
目标：寻找一组设施 \(S\)，使得 \[ \sum_{i \in S} f_i + \sum_{j\in D} \min_{i \in S} \{c_{ij}\} \] 即每个用户都会去离自己最近（或者说最划算）设施，求最小化开店费用加上服务成本（即每个顾客要走的距离之和）的开店方案。
线性规划表述
令 \(y_i\) 表示设施 \(i\) 是否被选，\(x_{ij}\) 表示用户 \(j\) 是否到设施 \(i\) 去，则设施选址问题可以表述为下列线性规划（松弛整数限制）： \[ \begin{aligned} \text{minimize}\quad &\sum_{i\in F}f_iy_i + \sum_{j\in D}\sum_{i \in F}c_{ij}x_{ij} \\ \text{subject to}\quad &\sum_{i\in F}x_{ij} \ge 1 \quad \forall j\in D \\ &y_i - x_{ij} \ge 0 \quad \forall i\in F, j\in D \\ &x_{ij} \ge 0 \quad \forall i\in F, j\in D \\ &y_i \ge 0 \quad \forall i \in F \end{aligned} \] 其中第一个约束表示所有顾客至少要去一个设施。第二个约束表示只有一个设施开的时候用户才可以去。
其对偶为 \[ \begin{aligned} \text{maximize}\quad &\sum_{j \in D}\alpha_j \\ \text{subject to}\quad &\alpha_j - \beta_{ij} \le c_{ij}\quad \forall i \in F, j\in D \\ &\sum_{j\in D}\beta_{ij} \le f_i\quad \forall i\in F \end{aligned} \]
令 \((x^*,y^*)\) 和 \((\alpha^*,\beta^*)\) 为主规划和对偶规划的最优解。显然，在线性规划当中很可能出现 \(0<x^*_{ij}<1\) 即 “部分得到服务” 的情况。
近似算法的设计思路与分析
引理：如果 \(x_{ij}^* > 0\) 那么 \(\alpha_j^* \ge c_{ij}\)。
证明：由主互补松弛条件，若 \(x_{ij}^*>0\) 则 \(\alpha_j^*-\beta_{ij}^* = c_{ij}\)，又 \(\beta_{ij}^* \ge 0\)，得证。
定义顾客 \(j\) 所有部分光顾的设施为 \(j\) 的邻域 \(N(j)=\left\{ i \Big| x_{ij}^* > 0,i\in F\right\}\)。
很容易想到一个近似算法：对于每一个顾客，我们开放邻域中离他最近的设施。
由于我们的引理和弱对偶原理，我们的总服务成本 \(\le \sum_{j\in D}\alpha_j^* \le \mathrm{OPT}\)。如果我们开放设施的成本也有个上界就好了。
然而并不行。
考虑如下反例：
如果按照我们的算法，我们会为 \(j\) 和 \(j'\) 分别开放一个代价 \(24\) 的设施。而事实上开那个代价 \(25\) 的设施就够了。我们差不多浪费了两倍的钱，而这个倍数可以任意高（只要让代价稍高一点的设施处在所有顾客的邻域当中，而使每个顾客的邻域中都有比其代价略低的设施即可）。
但是我们知道，对于任何一组邻域不交的顾客，开放设施的代价确实是不大于 \(\mathrm{OPT}\) 的（为什么？因为那些设施只服务一个顾客，而那个顾客有可能 “部分” 光顾其他设施。比如说一个顾客光顾了 \(0.5\) 的设施 \(1\)（代价为 \(10\)）和 \(0.5\) 的设施 \(2\)（代价为 \(20\)），那么这个顾客就给目标函数贡献了 \(0.5\times10+0.5\times 20\)，显然这个时候如果我去开代价 \(10\) 的那个设施，开店费是 \(10\)，是小于最优目标函数的）
那我不妨先任选一组邻域不交的顾客（不妨称之为 “幸运顾客”）按照就近原则开放他们的设施，然后再让那些邻域和幸运顾客有交集的顾客（不妨称之为 “倒霉顾客”）去这些设施。
根据我们之前的分析，幸运顾客的服务成本一定不大于 \(\mathrm{OPT}\)，考虑倒霉顾客的服务成本。假设倒霉顾客 \(j\) 和幸运顾客 \(i\) 的邻域共享一个设施 \(b\)，幸运顾客可以去离他最近的设施 \(a\)。
那么根据三角不等式，让 \(j\) 去 \(a\) 的距离为 \[ c_{aj} \le c_{bj}+c_{bi}+c_{ai} \] 根据引理， \[ \begin{aligned} c_{aj} &\le c_{bj}+c_{bi}+c_{ai} \\ &\le \alpha_j^* + \alpha_i^* + \alpha _i^* \\ &\stackrel{?}{\le} 3\alpha_j^* \end{aligned} \] 最后一步是我们希望得出的，因为如果这样，那么所有顾客的服务成本的上界就是（不妨令幸运顾客的集合为 \(D_1\)，不幸运顾客的集合为 \(D_2\)）： \[ \begin{aligned} \sum_{j\in D_1} \alpha_j^* + \sum_{j\in D_2}3\alpha_j^* \le \sum_{j\in D_1}3 \alpha_j^* + \sum_{j\in D_2}3\alpha_j^* = \mathrm{OPT}_{\text{dual}} \le \mathrm{OPT} \end{aligned} \] 但是按照目前的信息最后一步并不总是成立的。
那怎么办？改算法呗。我们只需要保证所有幸运顾客的 \(\alpha^*\) 都小于等于倒霉顾客的 \(\alpha^*\)，也就是说排一下序就好了。
于是我们就得到了我们的算法：
- 解原线性规划和对偶线性规划，得到 \((x^*,y^*),(\alpha^*,\beta^*)\)。
- 选一个 \(\alpha^*\) 最小的顾客并开放他邻域当中离他最近的店。
- 暂时移除所有和这个顾客有相交邻域的顾客。
- 持续以上两步直至所有顾客都被选中或移除。
- 让所有被移除的顾客去离他们最近的已开放设施。
这个算法的近似是多少呢？上面的分析已经说明了这个方案的设施成本不大于 \(\mathrm{OPT}\)，而服务成本不大于 \(3\mathrm{OPT}\)，因此总的来说这就是一个 \(4\) 倍近似算法。
近似难度
定理（Guha, Khuller 1999）：如果设施选址问题存在近似比小于 \(1.463\) 的算法，则 \(\mathsf{P}=\mathsf{NP}\)。