整数规划的ℓ1稀疏性近似界与在线作业调度的承诺模型分析

### 整数规划的ℓ1稀疏性近似界与在线作业调度的承诺模型分析 在优化问题的研究中，整数规划（PIPs）的近似算法以及在线作业调度问题一直是重要的研究方向。本文将深入探讨PIPs的ℓ1稀疏性近似界，以及在线作业调度中不同承诺模型对算法性能的影响。 #### 1. PIPs的ℓ1稀疏性近似界 ##### 1.1 大宽度情况（$W \geq 2$） - **定理2**：当设置$\alpha_1 = \frac{1}{c_1\Delta_1}$（其中$c_1 = 4e^{1 + \frac{1}{e}}$）时，对于宽度$W \geq 2$的PIPs，`round-and-alter-by-sorting(A, b, α1)`是一个随机的$(\frac{\alpha_1}{2})$ - 近似算法。 - **证明思路**：固定$j \in [n]$，根据引理2和$\Delta_1$的定义，可得$\sum_{i = 1}^{m} Pr[E_{ij}|X_j = 1] \leq \sum_{i = 1}^{m} \frac{A_{i,j}}{2\Delta_1} \leq \frac{1}{2}$。再由引理1（即对每个物品的拒绝概率之和进行上界约束为$\gamma$，可得到$\alpha_1(1 - \gamma)$ - 近似），从而得到所需结果。 - **改进的近似界**： - 通过设置$\alpha_1 = \frac{1}{c_2(1 + \frac{\Delta_1}{W})^{\frac{1}{W - 1}}}$（其中$c_2 = 4e^{1 + \frac{2}{e}}$），可以改进上述界。随着$W$的增加，缩放因子会变大。 - **定理3**：当设置$\alpha_1$为上述值时，对于宽度$W \geq 2$的PIPs，`round-and-alter-by-sorting(A, b, α1)`是一个随机的$(\frac{\alpha_1}{2})$ - 近似算法。证明过程是在定理2的证明中用引理3替换引理2。 - **特定情况下的近似**：当$W \geq \Omega(\frac{1}{\epsilon^2} \ln(\frac{\Delta_1}{\epsilon}))$时，使用`round-and-alter-by-sorting`算法，缩放因子$\alpha_1 = 1 - \epsilon$。 - **引理4**：设$0 < \epsilon < \frac{1}{e}$，$\alpha_1 = 1 - \epsilon$，$W = \frac{2}{\epsilon^2} \ln(\frac{\Delta_1}{\epsilon}) + 1$，则在`round-and-alter-by-sorting(A, b, α1)`中，有$Pr[E_{ij}|X_j = 1] \leq \frac{e \cdot \epsilon A_{i,j}}{\Delta_1}$。 - **定理4**：设$0 < \epsilon < \frac{1}{e}$，$W = \frac{2}{\epsilon^2} \ln(\frac{\Delta_1}{\epsilon}) + 1$，当设置$\alpha_1 = 1 - \epsilon$和$c = e + 1$时，`round-and-alter-by-sorting(A, b, α1)`是一个随机的$(1 - c\epsilon)$ - 近似算法。 ##### 1.2 小宽度情况（$W = 1 + \epsilon$） - 当宽度较小时，不能使用大宽度情况下基于简单排序的方案。此时，将每个约束中的坐标分为“小”和“大”两类。 - 设置$\alpha_2 = \frac{\epsilon^2}{c_3\Delta_1}$（其中$c_3 = 8e^{1 + \frac{2}{e}}$）。对于每个约束$i \in [m]$，定义$S_i = \{j : A_{i,j} \leq \frac{\epsilon}{2}\}$和$B_i = \{j : A_{i,j} > \frac{\epsilon}{2}\}$。 - **算法`round-alter-small-width`**： ```plaintext round-alter-small-width(A, b, ϵ, α2): let x be the optimum fractional solution of the natural LP relaxation for j ∈[n], set x′j to be 1 independently with probability α2xj and 0 otherwise x′′ ←x′ for i ∈[m] do if |Si| = 0 then s ←0 else sort and renumber such that Ai,1 ≤· · · ≤Ai,n s ←max{∑ℓ∈Si : ∑j = 1ℓ Ai,jx′j ≤ϵ} end if if |Bi| = 0, then t = 0, otherwise let t be an ```