PACT 07/09 设施选址问题

Posted on 2020-07-29 Edited on 2022-06-14 Views:

定义

输入：二分图，顶点集分为设施集和客户集。设施的开放费用为 f_i ，用户到设施的有权为 $c_{ij}$ 的边代表距离。边权满足三角不等式。

目标：寻找一组设施，使得

$\sum_{i \in S} f_i + \sum_{j\in D} \min_{i \in S} \{c_{ij}\}$

即每个用户都会去离自己最近（或者说最划算）设施，求最小化开店费用加上服务成本（即每个顾客要走的距离之和）的开店方案。

线性规划表述

令 y_i 表示设施是否被选， $x_{ij}$ 表示用户是否到设施去，则设施选址问题可以表述为下列线性规划（松弛整数限制）：

$\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$ ，得证。

定义顾客所有部分光顾的设施为的邻域 $N(j)=\left\{ i \Big| x_{ij}^* > 0,i\in F\right\}$ 。

很容易想到一个近似算法：对于每一个顾客，我们开放邻域中离他最近的设施。

由于我们的引理和弱对偶原理，我们的总服务成本 $\le \sum_{j\in D}\alpha_j^* \le \mathrm{OPT}$ 。如果我们开放设施的成本也有个上界就好了。

然而并不行。

考虑如下反例：

如果按照我们的算法，我们会为和分别开放一个代价的设施。而事实上开那个代价的设施就够了。我们差不多浪费了两倍的钱，而这个倍数可以任意高（只要让代价稍高一点的设施处在所有顾客的邻域当中，而使每个顾客的邻域中都有比其代价略低的设施即可）。

但是我们知道，对于任何一组邻域不交的顾客，开放设施的代价确实是不大于 $\mathrm{OPT}$ 的（为什么？因为那些设施只服务一个顾客，而那个顾客有可能“部分”光顾其他设施。比如说一个顾客光顾了 0.5 的设施（代价为）和 0.5 的设施（代价为），那么这个顾客就给目标函数贡献了 $0.5\times10+0.5\times 20$ ，显然这个时候如果我去开代价的那个设施，开店费是，是小于最优目标函数的）

那我不妨先任选一组邻域不交的顾客（不妨称之为“幸运顾客”）按照就近原则开放他们的设施，然后再让那些邻域和幸运顾客有交集的顾客（不妨称之为“倒霉顾客”）去这些设施。

根据我们之前的分析，幸运顾客的服务成本一定不大于 $\mathrm{OPT}$ ，考虑倒霉顾客的服务成本。假设倒霉顾客和幸运顾客的邻域共享一个设施，幸运顾客可以去离他最近的设施。

那么根据三角不等式，让去的距离为

$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}$

最后一步是我们希望得出的，因为如果这样，那么所有顾客的服务成本的上界就是（不妨令幸运顾客的集合为

，不幸运顾客的集合为

）：

$\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}$