数据广播与大规模数据流Lp差异近似算法解析

### 数据广播与大规模数据流Lp差异近似算法解析 #### 1. 数据广播问题中的下界与近似算法 在数据广播问题中，我们面临着如何高效调度消息广播以最小化成本的挑战。首先，通过一系列步骤可以得到调度成本的下界。 - **步骤分析**： - 经过步骤 1 的变换，利用反证法得到步骤 2。 - 步骤 3 中，我们剩下 $n_i$ 个包含 $\ell_i$ 个 $M_i$ 数据包的块。设 $t_k$ 为第 $k$ 个块开始到第 $(k + 1)$ 个块开始之间的时间。根据引理 2，$M_i$ 的期望服务时间为 $\sum_{k = 1}^{n_i} \left(\frac{t_k^2}{2T}\right) + \ell_i - \frac{n_i\ell_i(\ell_i - 1)}{2T}$，在约束条件 $\sum_{k = 1}^{n_i} t_k = T$ 下，当所有 $t_k = \frac{T}{n_i}$ 时该式取得最小值。定义 $\tau_i = \frac{T}{n_i\ell_i}$，则调度 $S$ 的成本下界为 $COST(S) > \sum_{k = 1}^{n_i} \left\{p_i \left(\frac{\tau_i\ell_i}{2} + \ell_i - \frac{\ell_i - 1}{2\tau_i}\right) + \frac{c_i}{\tau_i}\right\}$。同时，$n_i\ell_i \leq T$ 和 $\sum_{i = 1}^{m} n_i\ell_i \leq WT$ 意味着 (i) $\tau_i > 1$ 和 (ii) $\sum_{i = 1}^{m} \frac{1}{\tau_i} \leq W$。通过对这些约束条件进行最小化，可以得到任何调度成本的下界。 - **近似算法**： - **随机算法**： - **输入**：一些正数 $\tau_1, \ldots, \tau_m$，满足 $\sum_{i = 1}^{m} \frac{1}{\tau_i} \leq 1$。设 $\tau_0 > 0$ 使得 $\frac{1}{\tau_0} = 1 - \sum_{i = 1}^{m} \frac{1}{\tau_i}$。 - **输出**：对于 $t = 1$ 到 $\infty$，以概率 $\frac{1}{\tau_i}$ 抽取 $i \in \{0, 1, \ldots, m\}$。如果 $i > 1$，则在时隙 $t$ 调度消息 $M_i$ 的下一个数据包（按循环顺序）；否则，在时隙 $t$ 空闲。 - **性能**：给定 $m$ 个消息 $M_1, \ldots, M_m$，由随机算法生成的单通道调度 $S$ 的期望成本为 $E [COST(S)] = \frac{1}{2} + \sum_{i = 1}^{m} \left(p_i\tau_i\ell_i + \frac{c_i}{\tau_i}\right)$。如果 $\tau = \tau^*$ 实现了下界 $LB(M)$，则 $E [COST(S)] \leq 2 \cdot LB(M) - \frac{3}{2}$。 - **贪心算法**： - **输入**：一些正数 $\tau_1, \ldots, \tau_m$，满足 $\sum_{i = 1}^{m} \frac{1}{\tau_i} \leq 1$。设 $c_0 = p_0 = 0$ 且 $\tau_0 > 0$ 使得 $\frac{1}{\tau_0} = 1 - \sum_{i = 1}^{m} \frac{1}{\tau_i}$。 - **输出**：对于 $t = 1$ 到 $\infty$，选择 $i \in \{0, 1, \ldots, m\}$ 使得 $(c_i - p_i\tau_i \sum_{j = 1}^{\ell_i} s_{t - 1}^{i,j})$ 最小。如果 $i > 1$，则在时隙 $t$ 调度 $M_i$ 的下一个数据包（按循环顺序）；否则，在时隙 $t$ 空闲。 - **性能**：由贪心算法生成的单通道调度 $S$ 的成本为 $COST(S) \leq \frac{1}{2} + \sum_{i = 1}^{m} \left(p_i\tau_i\ell_i + \frac{c_i}{\tau_i}\right)$。如果 $\tau = \tau^*$ 实现了下界 $LB(M)$，则 $COST(S) \leq 2 \cdot LB(M) - \frac{3}{2}$。 - **确定性周期近似算法**：可以在多项式时间内构造一个周期调度，其成本 $\leq 2 \cdot LB(M)$，周期是消息总长度和成本的多项式（$\frac{14}{3} (\sum_{i = 1}^{m} \ell_i)^2 + 2 \sum_{i = 1}^{m} c_i\ell_i$）。 - **构造步骤**：