近似算法及其举例
主要來源于我們上課的PPT
1、負載均衡問題
有mmm個獨立的機器，nnn個任務，解決第 jjj 個任務所需要的時間為tjt_jtj?.
- 一個任務只能在一臺機器上連續的進行處理
- 一臺機器在同一個時間段只能處理一個任務（不能并行）
要求：將這nnn個任務安排給mmm臺機器，并且最小化負載均衡。
定義：
J(i)J(i)J(i)：分配給第 iii 臺機器的任務 組成的集合。
L(i)L(i)L(i)：第 iii 臺機器的負載，有 L(i)=∑j∈J(i)tjL(i) = \sum_{j \in J(i)}t_jL(i)=∑j∈J(i)?tj?。
LLL：負載均衡（makespan），有L=maxiL(i)L = max_iL(i)L=maxi?L(i)。
算法一：List Scheduling
每次將任務分配給 當前 負載最小 的機器。【算法復雜度O(nlog(m))O(nlog(m))O(nlog(m)) 】。
結論：該算法是 2倍近似最優的，既 2?approximation2-approximation2?approximation.
證明：
引理1 最優的負載均衡L?≥maxjtjL^* \geq max_jt_jL?≥maxj?tj?
引理2 最優的負載均衡L?≥1m∑j=1ntjL^* \geq \frac{1}{m}\sum_{j=1}^nt_jL?≥m1?∑j=1n?tj? (反證法可證明)
假設具有最大負載的機器 iii 完成的最后一個任務是 jjj，有：
L?tj<=1m∑k=1mLk=1m∑p=1n?1tp≤L?L - t_j <= \frac{1}{m}\sum_{k=1}^mL_k =\frac{1}{m}\sum_{p=1}^{n-1}t_p \leq L^* L?tj?<=m1?k=1∑m?Lk?=m1?p=1∑n?1?tp?≤L?
又根據引理1：
tj≤L?t_j \leq L* tj?≤L?
故：
L?tj+tj≤L?+L?=2L?L - t_j + t_j \leq L^* + L^* = 2L^* L?tj?+tj?≤L?+L?=2L?
所以list?schedulinglist-schedulinglist?scheduling 算法是2倍近似最優的。
算法二：LPT Rule
先將nnn個任務按處理時間的降序排列，再執行list?schedulinglist-schedulinglist?scheduling 算法.【算法復雜度n?max(log(n),log(m))n*max(log(n), log(m))n?max(log(n),log(m))】
結論：LPT Rule 算法是32\frac{3}{2}23?倍近似最優的，既32?approximation\frac{3}{2} -approximation23??approximation.
證明：
引理3 如果n>mn > mn>m，則L?≥2tm+1L^* \geq 2t_{m+1}L?≥2tm+1?
為什么成立？ 考慮前m+1m+1m+1個任務，【注意這些任務已經按處理時間的降序排列了，既t1≥t2≥t3≥???≥tm≥tm+1t_1 \geq t_2 \geq t_3 \geq ··· \geq t_m \geq t_{m+1}t1?≥t2?≥t3?≥???≥tm?≥tm+1?】，顯然，有一臺機器得到了2個任務，假設這兩個任務是 ppp 和 qqq，有：L?≥tp+tq>=tm+1+tm+1L^* \geq t_p + t_q >= t_{m+1} + t_{m+1}L?≥tp?+tq?>=tm+1?+tm+1?，既L?≥2tm+1L^* \geq 2t_{m+1}L?≥2tm+1?.
考慮最后一個任務nnn。在上一個算法中，我們已經證明了：L?≥L?tnL^* \geq L - t_nL?≥L?tn?
又根據引理3：
L?>=2tm+1≥2tn?12L?≥tnL^* >= 2t_{m+1} \geq 2t_n \\ \Longrightarrow \frac{1}{2}L^* \geq t_n L?>=2tm+1?≥2tn??21?L?≥tn?
故：
L?+12L?≥L?tn+tn=LL^* + \frac{1}{2}L^* \geq L - t_n + t_n = L L?+21?L?≥L?tn?+tn?=L
所以LPT Rule 算法是32\frac{3}{2}23?倍近似最優的。
32\frac{3}{2}23?不是LPT Rule 算法的近似上界，有人證明它的近似上界是43\frac{4}{3}34?。 【可能考判斷題】
3、帶權重的點覆蓋
給一個帶有點權的圖GGG，求出權重最小的點覆蓋。
如圖，每個頂點都有一個權值，左邊的點覆蓋權重等于10，右邊的點覆蓋權重等于11。所以這個圖的權重最小的點覆蓋是{2,2,4}\{2,2,4\}{2,2,4}
定義：
wiw_iwi?：頂點 iii 的權值
EiE_iEi?：以頂點 iii 作為端點的邊的集合
tightitight_itighti?：如果頂點 iii 滿足 ∑e∈Eipe=wi\sum_{e \in E_i}p_e = w_i∑e∈Ei??pe?=wi?，那么頂點 iii 就是tighttighttight的。
算法一：定價法
給 每一條邊 都確定一個價格 pep_epe?，同時保證：∑e∈Eipe≤wi\sum_{e \in E_i}p_e \leq w_i∑e∈Ei??pe?≤wi?。剛開始，令所有的邊的價格pep_epe?等于0。然后，從EEE中任意挑選出一條邊e′e'e′，盡可能增加它的價格，直到這條邊的某個端點tighttighttight。當這條邊的某個端點tighttighttight時，將這條邊從EEE中踢出去，既E=E?e′E = E - {e'}E=E?e′，重復上述步驟，直到E=ΦE = \PhiE=Φ。權重最小的點覆蓋 就是那些 tighttighttight 的頂點。
結論：定價法是2倍近似最優的，既 2?approximation2-approximation2?approximation。
證明：
引理1 對于任意的點覆蓋SSS，都有 ∑e∈Epe≤w(S)\sum_{e \in E}p_e \leq w(S)∑e∈E?pe?≤w(S)
為什么成立？∑e∈Epe≤∑i∈S(∑e∈Eipe)≤∑i∈Swi=w(S)\sum_{e \in E}p_e \leq \sum_{i \in S}(\sum_{e \in E_i}p_e) \leq \sum_{i \in S}w_i = w(S)∑e∈E?pe?≤∑i∈S?(∑e∈Ei??pe?)≤∑i∈S?wi?=w(S)
注意上述推導使用了點覆蓋的定義：SSS覆蓋了所有的邊
記那些tighttighttight的頂點 組成的集合為SSS，實際最小的權重點覆蓋為S?S^*S?，有：
w(S)=∑i∈Swi=∑i∈S(∑e∈Eipe)≤∑i∈V(∑e∈Eipe)=2∑e∈Epe≤2w(S?)w(S) = \sum_{i \in S}w_i = \sum_{i \in S}(\sum_{e \in E_i}p_e) \leq \sum_{i \in V}(\sum_{e \in E_i}p_e) = 2\sum_{e \in E}p_e \leq 2w(S^*) w(S)=i∈S∑?wi?=i∈S∑?(e∈Ei?∑?pe?)≤i∈V∑?(e∈Ei?∑?pe?)=2e∈E∑?pe?≤2w(S?)
所以定價法是2倍近似最優的。
算法二：線性規劃（LP）
用一個二進制變量表示 一個頂點是否在最小權重點覆蓋中，既：
xi={0如果頂點i不在最小權重點覆蓋中1如果頂點i在最小權重點覆蓋中x_i= \begin{cases} 0 & 如果頂點 i 不在最小權重點覆蓋中 \\ 1 & 如果頂點 i 在最小權重點覆蓋中 \end{cases} xi?={01?如果頂點i不在最小權重點覆蓋中如果頂點i在最小權重點覆蓋中?
建立如下的 ILP：
{minize(∑i∈Vwi?xi)xi+xj≥1(i,j)∈Exi∈{0,1}i∈V\begin{cases} minize(\sum_{i \in V}w_i*x_i) \\ x_i + x_j \geq 1 & (i,j) \in E \\ x_i \in \{0,1\} & i \in V \end{cases} ??????minize(∑i∈V?wi??xi?)xi?+xj?≥1xi?∈{0,1}?(i,j)∈Ei∈V?
假設實際的最小權重點覆蓋為S?S^*S?，如果x?x^*x?是ILP的解，則S?={i∈V∣xi?=1}S^* = \{i \in V | x_i^* = 1\}S?={i∈V∣xi??=1}.
經前人證明，ILP是NPHNPHNPH問題，而LP可以在多項式時間內得到解決，所以將xxx的范圍放縮到大于0的實數域，既只要求xi≥0x_i \geq 0xi?≥0，從而將ILP轉化為LP：
{minize(∑i∈Vwi?xi)xi+xj≥1(i,j)∈Exi≥0i∈V\begin{cases} minize(\sum_{i \in V}w_i * x_i) \\ x_i + x_j \geq 1 & (i,j) \in E \\ x_i \geq 0 & i \in V \end{cases} ??????minize(∑i∈V?wi??xi?)xi?+xj?≥1xi?≥0?(i,j)∈Ei∈V?
結論：假設x?x^*x?是LP的最優解，則令最小權重點覆蓋S={i∈V∣xi?≥12}S = \{i \in V |x_i^* \geq \frac{1}{2} \}S={i∈V∣xi??≥21?}，有S≤2S?S \leq 2S^*S≤2S?，既LP算法是2倍近似最優的。
證明：
引理1 ILP的最優解 ≥\geq≥ LP的最優解
引理2 考察EEE中的任何一條邊(i,j)(i,j)(i,j)，有xi?≥12x_i^* \geq \frac{1}{2}xi??≥21? ororor xj?≥12x_j^* \geq \frac{1}{2}xj??≥21?
為什么成立？LP中有約束條件xi+xj≥1x_i + x_j \geq 1xi?+xj?≥1，所以xi?+xj?≥1x_i^* + x_j^* \geq 1xi??+xj??≥1，顯然兩者中必有一個12\frac{1}{2}21?。
根據引理1和引理2，有：
∑i∈S?wi≥∑i∈Swi?xi?≥12∑i∈Swi\sum_{i \in S^*}w_i \geq \sum_{i \in S}w_i * x_i^* \geq \frac{1}{2}\sum_{i \in S}w_i i∈S?∑?wi?≥i∈S∑?wi??xi??≥21?i∈S∑?wi?
所以LP算法是2倍近似最優的。
總結
- 上一篇： 宽带连接 已经阻止
- 下一篇： 让你一分钟认识电子身份验证系统EID