負載平衡近似（load-balancing approximation）

你有一堆已知時長的工作和 m 台相同的機器，必須把每個工作指派給某台機器。每台機器把分到的工作一個接一個跑完；最後一台完工的時間叫做最大完工時間（makespan），你想讓這個完工時間越小越好——把整批盡快做完。決定最佳指派是 NP 困難的，但一個極簡單的貪婪規則能讓你進到 2 倍以內，再小修一下能到 4/3。

貪婪規則（表列排程）是：把工作一個一個拿出來，每個都指派給目前負載最輕的機器。為何這永不超過最佳值的兩倍？看那台最後完工的機器，以及它被指派的「最後」一個工作 j。在 j 被放上去的那一刻，那台機器是負載最輕的，所以它「放 j 之前」的負載最多是所有機器的平均負載，也就是（總工作量）/ m。兩個乾淨的 OPT 下界把一切釘住：最佳完工時間至少是平均負載（總量 / m），因為某台機器必須至少做它那一份；而且至少是最大的單一工作（那個工作總得在某處跑）。完工機器的時間是它「放 j 之前」的負載加上工作 j，最多是 平均 + (最大工作) <= OPT + OPT = 2 * OPT。所以樸素貪婪是 2 近似。若你在放置之前先把工作「從最長到最短」排序（最長處理時間優先），同樣風格的論證會把保證收緊到 4/3 * OPT，因為等小工作到來時機器已經相當平衡了。

這是最實用的近似結果之一，是排程器與負載平衡器實際把工作分散到伺服器或核心上的骨幹。誠實的提醒：那兩個下界（平均負載與最大工作）又是「OPT 替身」技巧，是你無法直接求得之值的可計算代替品。樸素貪婪能線上運作——它能在每個工作到來時就放置，無需預知未來——這正是它被廣泛部署的原因；先排序則需要事先拿到所有工作，但換來更好的 4/3 比值。一如既往，這些是最壞情況的上限；在典型工作負載上貪婪落得離最佳近得多。