為什么使用近似算法
無法找到一個(gè)NP難問題的多項(xiàng)式時(shí)間普適算法，因此我們思考犧牲算法的精確度，以在可計(jì)算時(shí)間內(nèi)找到一個(gè)近似解锻拘。對(duì)于一個(gè)近似算法署拟，滿足：
- 在多項(xiàng)式時(shí)間內(nèi)完成
- 具有普適性（能解決這類問題的任何實(shí)例）
- 有一個(gè)確切的近似程度（準(zhǔn)確解的多少倍）
找一個(gè)NP難問題的近似算法推穷，只需要證明其近似程度（多少倍地接近精確值）蟹腾，而不用知道這個(gè)精確值究竟是多少区宇。
近似算法舉例
Ⅰ. 負(fù)載均衡問題
臺(tái)相同的機(jī)器炉爆，
個(gè)不同的工作及完成它所需的時(shí)間
卧晓，問滿足如下條件的最短工作時(shí)長衩辟。
- 一個(gè)工作必須連續(xù)執(zhí)行直到完成艺晴；
- 一臺(tái)機(jī)器一次只能處理一個(gè)工作封寞。
2倍近似算法——List Scheduling
List Scheduling 是一種貪心策略狈究，它的核心思想是將各個(gè)工作依次安排到累計(jì)工作時(shí)長最短的機(jī)器中抖锥，下面的動(dòng)圖顯示了這一過程磅废≌悖可以發(fā)現(xiàn)竟趾，這種貪心的初衷只考慮了眼前的最小值，而局部最優(yōu)解并不一定是最終的最優(yōu)解宫峦。
我們假設(shè)完成所有工作的最短工作時(shí)長岔帽，來自第i臺(tái)機(jī)器，證明前导绷，先確定兩個(gè)結(jié)論犀勒。設(shè)完成所有工作的最短時(shí)間跨度（makespan）為
，結(jié)束時(shí)各臺(tái)機(jī)器的時(shí)間跨度為
妥曲，有：
-
贾费，
不小于完成最長的工作所需時(shí)間
-
，
（機(jī)器平分工作）
設(shè)最后一個(gè)加入到第臺(tái)機(jī)器運(yùn)行的是工作
（注意：不一定是所有工作的最后一個(gè)）逾一，那么有
?????????? ?????? ①
??????????????????? ?? ②
???????????????????? ???? ③
所以锡足。
3/2倍近似算法——LPT Rule
上述貪心策略存在一個(gè)很明顯的漏洞爽蝴，當(dāng)最后加入的工作所花時(shí)間最長時(shí)发框，效果很差铣减，直逼2倍TT鳖枕。因此我們希望先安排長工作，將所有工作按花費(fèi)時(shí)間降序排列，再執(zhí)行上述貪心算法，這就是LPT(Longest Processing Time) Rule的核心思想。
當(dāng)時(shí)，則每臺(tái)機(jī)器最多安排一個(gè)工作，容易找到最優(yōu)解。當(dāng)
時(shí)天通，先將m個(gè)工作安排到m臺(tái)機(jī)器，那么對(duì)第
個(gè)工作，有
. 則對(duì)③，
Graham在1969年照雁，計(jì)算出LPT Rule是負(fù)載均衡問題的一個(gè)4/3近似算法裕坊。太復(fù)雜了静浴，老師都放棄了···
Ⅱ. 中心選擇問題
給定平面（或空間）上的n個(gè)點(diǎn)和中心個(gè)數(shù)k，問如何放置這k個(gè)中心，使得所有點(diǎn)被以這k個(gè)點(diǎn)為中心的圓盤覆蓋且最大的圓盤半徑最虚环骸（不是所有圓盤的半徑之和）齐鲤。對(duì)所有點(diǎn)丑罪，被相距最近的中心點(diǎn)形成的圓盤覆蓋拧抖。
貪心策略——依次選擇離其中心最遠(yuǎn)的點(diǎn)為新的中心
因?yàn)橹行倪x擇的目標(biāo)是最小化離其中心最遠(yuǎn)的點(diǎn)與該中心的距離腐碱，所以每次加入新的中心時(shí)，直接貪心選擇這樣離其中心最遠(yuǎn)的點(diǎn)乎芳。
依次選擇離其中心最遠(yuǎn)的點(diǎn)為新的中心，這樣的貪心算法是一個(gè)2倍近似算法攒钳。
設(shè)集合和
分別是貪心算法和真實(shí)的最佳中心实愚，
和
分別是貪心算法和真實(shí)情況里離中心最遠(yuǎn)的距離（最小覆蓋半徑）没宾。需要證明結(jié)論
≤2
??????
Ⅲ. 帶權(quán)點(diǎn)覆蓋問題
對(duì)于點(diǎn)覆蓋問題（一個(gè)點(diǎn)的集合使得圖中所有邊至少有一個(gè)端點(diǎn)在集合內(nèi)）胁出，帶權(quán)點(diǎn)覆蓋問題中型型，需要滿足這個(gè)集合中所有點(diǎn)的權(quán)值之和最小。
競價(jià)法是帶權(quán)點(diǎn)覆蓋問題的2倍近似算法
競價(jià)簡單理解為邊給相鄰的點(diǎn)支付保護(hù)費(fèi)全蝶，以保證自己能被至少一個(gè)點(diǎn)保護(hù)（覆蓋）闹蒜；而點(diǎn)收到來自各條相鄰邊支付的保護(hù)費(fèi)之和剛好是它的權(quán)值，才能保護(hù)它們抑淫。這樣绷落，那些收到保護(hù)費(fèi)剛好是自身權(quán)值的點(diǎn)構(gòu)成一個(gè)頂點(diǎn)覆蓋。下面證明用競價(jià)法是帶權(quán)點(diǎn)覆蓋問題的2倍近似算法始苇。
引理 對(duì)于任意點(diǎn)覆蓋和邊
給出的價(jià)格
砌烁，有
.
可通過兩個(gè)恒等變換簡單證明，因?yàn)楹芏帱c(diǎn)共用了邊支付的價(jià)格，所以一定有所有點(diǎn)給出的競價(jià)不大于點(diǎn)覆蓋權(quán)值之和函喉。
競價(jià)法過程
選出還未被保護(hù)的邊避归，提最少的價(jià)使得其相鄰點(diǎn)至少有一個(gè)能保護(hù)它，這些能保護(hù)（覆蓋）臨近邊的點(diǎn)稱其為緊（tight）的管呵，將其加入點(diǎn)覆蓋集合梳毙。循環(huán)操作，直至所有邊都能被保護(hù)捐下。偽代碼如下：
競價(jià)法求解點(diǎn)覆蓋問題账锹，舉例如下：
上圖中，最后tight的點(diǎn){a, b, d}坷襟，即為最小的帶權(quán)點(diǎn)覆蓋奸柬，權(quán)為10. 注意：邊給出的競價(jià)之和不是點(diǎn)覆蓋的權(quán)。
競價(jià)法2倍近似的證明
設(shè)最優(yōu)點(diǎn)覆蓋和競價(jià)法獲得的點(diǎn)覆蓋
啤握，有
.
??????
倒數(shù)第二個(gè)恒等變換的依據(jù)是每條邊計(jì)算了兩次鸟缕，最后到的放縮依據(jù)是，每條邊給出的價(jià)格不大于其任一相鄰點(diǎn)的權(quán)值（給錢的事都是達(dá)到目的后越少越好）排抬。注意 并不是所有的邊都會(huì)出錢，因?yàn)辄c(diǎn)一旦具備保護(hù)（覆蓋）能力后授段，與其相鄰的所有邊均被保護(hù)（覆蓋）蹲蒲，從上面的圖也能看出。
