原始對偶法（primal-dual method）

精確解一個線性規劃再捨入，是行得通——但對像頂點覆蓋這樣的問題動用一個完整的 LP 求解器感覺太重。原始對偶法在「從不解 LP」的情況下取得同類保證：它利用一個問題與其「對偶」之間的對偶性，同時建出整數解與其品質的證書。結果通常是一個簡單、快速的組合演算法，其近似因子從對偶的記帳中自然掉出。

用白話講這個想法。每個線性規劃（原始，例如最小化覆蓋）都有一個叫對偶的夥伴 LP（例如邊上的一個裝填問題），而弱對偶性保證「任何」可行對偶解都給出原始最佳值的一個下界。原始對偶法同時跑兩者：它從對偶變數全為零、原始解為空開始，然後反覆「抬升」對偶變數（讓下界長大），直到某個對偶約束變緊，而每當一個約束變緊，就把對應的元素加進原始解。對頂點覆蓋：在每條尚未覆蓋的邊上維持一筆「預算」y_e；抬升這些預算，直到某頂點上所有相鄰預算之和等於它的成本（它「變緊」），就把那個頂點加進覆蓋並移除它的邊。你能證明每個被選頂點的成本都由邊的預算支付，每條邊最多支付兩個頂點，所以覆蓋成本最多是對偶總和的兩倍——而對偶總和是 OPT 的下界。這又給出 2 近似，現在不需 LP 求解器，只要一個抬升預算的迴圈。

這方法為何被珍視：它產生快速、常常看起來像貪婪的演算法，並帶有證明過的比值，而它建出的對偶解就是自身的正確性證書——你結束時手上同時握著一個答案和一份近最佳的證明。它是集合覆蓋、史坦納樹、設施選址、最短路徑式網路設計等經典結果背後的引擎。誠實的範圍：設計對偶與抬升排程需要真正的洞察，你拿到的比值取決於你利用的結構；原始對偶是一個強大的框架，不是自動配方，而且和所有鬆弛方法一樣，它最終受底層 LP 的整數性差距所限。