局部搜索近似

三个必须固定的对象 ​

对优化问题公理库优化问题Optimization problem在可行解集合上最小化或最大化目标函数的计算问题。，局部搜索先定义可行解集合 (\mathcal F)、目标函数 (C(S)) 和邻域 (N(S))。最小化问题中的 improving move 是满足 [ S'\in N(S),\qquad C(S')<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,\quad C(10)=3,\quad C(01)=3,\quad C(11)=0. ] 从 (00) 出发，两个邻居都更差，因此算法停止在费用 2；全局最优 (11) 的费用为 0，却需要同时翻转两位才能到达。

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

多项式终止 ​

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

例如要求 [ C(S')\le\left(1-\frac{\eta}{q(n)}\right)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.