局部搜索近似

形式陈述 ​

三个必须固定的对象 ​

对优化问题公理库优化问题Optimization problem在可行解集合上最小化或最大化目标函数的计算问题。，局部搜索先定义可行解集合 $\mathcal{F}$、目标函数 $C(S)$ 和邻域 $N(S)$。最小化问题中的 improving move 是满足

$$S^{\prime }\in N(S),C(S^{\prime })<C(S)$$

的替换。算法从一个可行解出发反复采用改善移动，直到不存在移动；终点只是相对所选邻域的局部最优。

近似算法还必须给出如何搜索邻域与何时停止。若一次邻域检查本身是 NP-hard，或改善量可以无限接近 0 而迭代次数无界，“最终到局部最优”并不构成多项式算法。

metric k-median 的 p-swap ​

给定候选设施 $F$、客户 $D$、度量距离 $d$ 与整数 $k$，解 $S\subseteq F$ 满足 $|S|=k$，费用为

$$C(S)=\sum _{j\in D}d(j,S).$$

一个 $p$-swap 从 $S$ 中关闭至多 $p$ 个设施，同时从 $F\setminus S$ 开启同样多个设施，再把每个客户分配给最近的开放设施。

当 $p$ 是常数，可以枚举 $n^{O(p)}$ 个交换并计算新费用。邻域越大，单轮越贵，但局部最优条件更强。经典分析表明，metric k-median 的 $p$-swap 局部最优可达到

$$3+\frac{2}{p}$$

量级的近似比公理库近似比Approximation ratio近似算法解值与最优值之间的最坏情形乘法保证。。

一次交换如何计算 ​

设当前开放设施为 $S=\{x,y\}$，考虑关闭 $x$、开启 $z$。原先由 $x$ 服务的客户要比较到 $z$ 与仍开放的 $y$ 的距离；原先由 $y$ 服务的客户也可能改投更近的 $z$。因此交换增量是所有客户新旧最近距离之差，不能只统计 $x$ 的旧客户。

实现可为每个客户保存最近与次近的当前设施。关闭一个设施时，受影响客户先退到次近候选，再与新设施比较；这加速 1-swap，但对一般 $p$-swap 仍需处理多个同时关闭设施。

从局部不等式到近似比 ​

令 $O$ 为最优设施集，把每个最优设施映射到 $S$ 中离它最近的设施。分析按映射入度把 $O$ 的设施分组，构造一族合法的至多 $p$ 交换，使每个最优设施被开启规定次数，而当前设施的关闭次数受到控制。

局部最优意味着每个交换的费用变化非负。把这些不等式按设计权重相加，用三角不等式把客户从当前设施绕到最优设施及其映射点，便把所有重分配项压回 $C(S)$ 与 $C(O)$。计数系数最终给出 $C(S)\le (3+2/p)C(O)$。

证明依赖 metric 的三角不等式，也依赖交换族确实可行。任意成本矩阵上不能沿用这条重分配界；允许关闭 $p$ 个却开启不同数量时，也已经改变了固定 $k$ 的可行域。

直觉

局部最优只排除了邻域中看得见的改善，因此质量完全取决于邻域能否用一组小交换覆盖全局最优与当前解的差异。近似证明把每个禁止的改善写成不等式，再按结构化权重相加；算法停下本身并不会自动产生任何全局比率。

例子与边界

局部最优可以很差 ​

局部最优的质量完全由邻域决定。考虑四个可行状态 $00,10,01,11$，邻域只允许翻转一个 bit，费用依次为

$$C(00)=2,C(10)=3,C(01)=3,C(11)=0.$$

从 $00$ 出发，两个邻居都更差，因此算法停止在费用 2；全局最优 $11$ 的费用为 0，却需要同时翻转两位才能到达。

这个具体陷阱不是 metric k-median 的近似下界，而是说明“严格改善直到停止”本身不携带任何近似比。k-median 的保证来自度量结构与 p-swap 交换论证，不来自 local optimum 这个名称。

多项式终止 ​

若目标值是范围多项式有界的整数，每次至少下降 1 就可用势函数公理库势能法Potential method用数据结构状态势能的变化修正实际成本以界定均摊成本。证明迭代数。一般有理或实数费用可能产生指数多个微小改善，因此常采用近似局部最优：只接受让费用下降至少某个相对阈值的移动。

例如要求

$$C(S^{\prime })\le (1-\frac{\eta }{q(n)})C(S)$$

可把迭代数控制为输入规模与 $1/\eta$ 的多项式；交换证明则会多出一个可控的 $O(\eta )$ 误差。阈值大小、初始解上界和数值编码长度都应出现在运行时间论证中。

推论与应用

facility location 与适用边界 ​

非容量 facility location 还要支付设施开启费，邻域可包含 open、close 与 swap。客户重分配节省必须与新增开启费共同比较；把 k-median 的“始终开放恰好 $k$ 个”约束直接搬来会漏掉费用项。

局部搜索适合能快速评价移动、又能由局部交换覆盖全局差异的问题。容量约束、非度量距离或大 $p$ 会让邻域搜索和可行性显著变难。随机选邻居、接受变差移动的模拟退火是另一种启发式，不自动继承这里的近似定理。

参考资料

• Vijay Arya, Naveen Garg, Rohit Khandekar, Adam Meyerson, Kamesh Munagala and Vinayaka Pandit, Local Search Heuristics for k-Median and Facility Location Problems, SIAM Journal on Computing, 2004.
• David P. Williamson and David B. Shmoys, The Design of Approximation Algorithms, Cambridge University Press, 2011.
• Emile Aarts and Jan Karel Lenstra (eds.), Local Search in Combinatorial Optimization, Princeton University Press, 1997.