欧几里得k-均值带惩罚问题的原始对偶算法

### 欧几里得 k - 均值带惩罚问题的原始对偶算法 在解决带惩罚的设施选址问题时，我们可以通过线性规划及其对偶问题来寻找解决方案。当每个设施的开放成本为 λ，连接成本为 $c(·, ·) = d^2(·, ·)$ 时，如果通过选择合适的 λ 使得开放的设施数量不超过 k，那么我们就得到了原问题的一个可行解。基于此思想，我们提出了一种拟多项式时间的 (6.357 + ε) - 近似算法。该算法以 JV 算法为基础，包含两个子例程：首先枚举 λ 以获得一系列设施解决方案 S，然后处理序列 S 使开放设施的数量恰好为 k。 #### 1. 拟多项式时间近似算法 在介绍主算法之前，我们先介绍一个新算法 JV - P(δ)，它是基于 JV(δ) 算法改进的原始对偶算法，用于解决每个设施开放成本都等于 λ 的带惩罚设施选址问题。 ##### 1.1 JV - P(δ) 算法 该算法包含两个阶段：对偶增长阶段（算法 1）和修剪阶段（算法 2）。 - **对偶增长阶段（算法 1）** 1. 初始时，令 α := 0，设置 $β_{ij} := [α_j - c(i, j)]^+ = max\{α_j - c(i, j), 0\}$。令 A := D 表示活跃客户集，θ 表示时间。从 0 开始，对于所有 $j \in A$，$α_j$ 和 θ 以相同的单位速度同时增长。当 $α_j = p_j$ 时，称 j 被冻结，$α_j$ 不再增加。若发生以下事件之一，j 从 A 中移除： - 事件 1：对于某个设施 $i \in F$，对偶约束 $\sum_{j \in D}[α_j - c(j, i)]^+ = λ$ 成立。此时称设施 i 是紧的或临时开放的。若 $α_j \geq c(i, j)$，则从 A 中移除 j，并记设施 i 为这些移除客户的见证，即 $w(j) = i$。 - 事件 2：活跃客户 $j \in A$ 与某个已紧的设施 i 形成紧边，即 $α_j - c(j, i) = 0$。此时将 j 从 A 中移除，并令 i 为其见证。 2. 当 $A = \varnothing$ 或对于所有 $j \in A$，j 都被冻结时，对偶增长阶段停止。 以下是对偶增长阶段的流程图： ```mermaid graph TD; A[初始化 α = 0, βij = [αj - c(i, j)]+] --> B[设置 A = D, θ = 0]; B --> C{αj 和 θ 增长}; C --> D{αj = pj?}; D -- 是 --> E[j 被冻结]; D -- 否 --> F{是否发生事件 1 或 2}; F -- 是 --> G[j 从 A 中移除]; F -- 否 --> C; E --> H{A = ∅ 或所有 j 被冻结?}; G --> H; H -- 是 --> I[对偶增长阶段停止]; H -- 否 --> C; ``` - **修剪阶段（算法 2）** 对偶增长阶段可能会开放比必要数量更多的设施，修剪阶段将选择这些设施的一个子集来开放。我们引入以下符号： - $F_y$：对偶增长阶段临时开放的设施集。 - $N(j) := \{i \in F : α_j - c(i, j) > 0\}$，对于所有 $j \in D$。 - $N(i) := \{j \in D : α_j - c(i, j) > 0\}$，对于所有 $i \in F$。 - 对于临时开放的设施 i，令 $t_i := max_{j \in N(i)} α_j$，若 $N(i) = \varnothing$，则 $t_i := 0$。所以，对于所有 $j \in N(i)$，有 $t_i \geq α_j$。对于客户 j 及其见证 $w(j)$，有 $α_j \geq t_{w(j)}$。 我们构建客户 - 设施图 G 和冲突图 H： - $G = (D \cup F_y, E)$：若 $i \in N(j)$，则设施 i 和客户 j 之间有一条边。 - $H = (F_y, E)$：若 $j \in N(i) \cap N(i')$ 且 $c(i, i') \leq δ min(t_i, t_{i'})$，则设施 i 和 $i'$ 之间有一条边。 直观上，δ 的大小会影响 H 中的边数，从而决定 H 中最大独立集的大小。因此，通过适当调整 δ，我们可以获得 JV - P(δ) 算法更好的近似比。 修剪阶段的具体步骤为：找到 H 的一个最大独立集 IS 并开放这些设施。定义惩罚客户集 $D_p$ 为：$D_p := \{j \in D : j \notin N(i), \forall i \in IS 且 α_j = p_j\}$。其余客户连接到 IS 中最近的设施。 下面是修剪阶段的步骤表格： |步骤|操作| |----|----| |1|找到冲突图 H 的最大独立集 IS| |2|定义惩罚客户集 $D_p$| |3|将其余客户连接到 IS 中最近的设施| 引理 1 表明，对于任何 $\lambda \geq 0$，算法 JV - P(δ) 为 DUAL - P(λ) 构造一个解 α，并输出开放设施集 IS 和惩罚客户集 $D_p$，使得： $\sum_{j \in D \setminus D_p} d(j, IS)^2 + \sum_{j \in D_p} p_j \leq \rho \cdot \left(\sum_{j \in D} α_j - \lambda|IS|\right)$ 其中，$\delta \geq 2$ 是一个参数，用于最小化 $\rho(\delta) = max\{(1 + \sqrt{\delta})^2, \frac{1}{\delta/2 - 1}\}$。可以验证，当 $\delta \approx 2.315$ 时，$\rho \approx 6.357$。 #### 2. 枚举 λ 我们枚举 $\lambda$ 的所有可能值，即 $\lambda = 0, 1 \cdot \epsilon_z, \cdots, L \cdot \epsilon_z$，其中 $\epsilon_z$ 是一个小步长，L 是一个较大的值。通过类似的分析，我们选择 $n \gg 1/\epsilon$，$\epsilon_z = n^{-3 - 30 log_{1 + \epsilon} n}$，$L = 4n^7 \cdot \epsilon_z^{-1}$。同时，可以保证当 $\lambda = 0$ 时，算法得到的解为 $IS = F$；当 $\lambda = L \cdot \epsilon_z$ 时，$|IS| \leq 1$。 我们还使用桶的概念来划分客户的 α 值。对于任何值 $x \in R$，定义： $B(x) := \begin{cases} 0, & \text{如果 } x < 1 \\ 1 + \lfloor log_{1 + \epsilon}(x) \rfloor, & \text{如果 } x \geq 1 \end{cases}$ 这里 $B(x)$ 是包含 x 的桶的索引，也是一个分段函数。 为了简化算法，我们对给定实例进行预处理，使得对于所有 $j \in D$ 和 $i \in F$，有 $1 \leq d(j, i)^2 \leq n^6$，这只会使近似比损失一个常数 $(1 + 100/n^2)$。 枚举 λ 的算法如下： 1. 初始时，$\lambda = 0$，设置 $α_{out}^j = min\{min_{i \in F} d(j, i)^2, p_j\}$，$IS = F$。 2. $α = α_{out}$，$\lambda = \lambda + \