α 近似保證（alpha-approximation guarantee）
當我們為近似比指定一個具體的數時，就稱這個演算法為 α 近似（alpha-approximation），其中 α（希臘字母）就是那個數。說「這是個 1.5 近似」就是一紙合約：餵給它任何合法輸入，它回傳的答案都會在最佳值的 1.5 倍因子之內。給 α 命名的全部用意，是為了乾淨地比較演算法——1.5 近似勝過 2 近似，因為它最壞情況的承諾更緊。
把兩類問題的合約寫清楚。對最小化，α 近似（α >= 1）保證對每個實例都有 ALG <= α * OPT：成本最多是最佳值的 α 倍。對最大化，它保證 ALG >= OPT / α（等價於 ALG >= (1/α) * OPT）：值至少是最佳值的 1/α 分。任何這類證明中微妙而關鍵的地方在於：你其實從來不知道 OPT——算出它正是你要避開的那個 NP 困難工作。所以證明是間接進行的：你找出某個「你算得出來」的量，並證明它是 OPT 的下界（最小化）或上界（最大化），再把你的演算法對著這個替身去界定。例如對頂點覆蓋，極大匹配中的邊數就是任何覆蓋大小的一個可計算下界。
兩個誠實的提醒。第一，α 不必是常數：對集合覆蓋，最佳保證是 α = ln n，會隨輸入規模成長，而且除非 P = NP，這已被證明是可能達到的最佳。第二，保證的好壞只到它證明的範圍為止——它在所陳述的問題與模型下成立，而一個 α 很漂亮的演算法仍可能因其他原因而緩慢或不實用。保證界定的是品質，不是執行時間；那是你要分開檢查的另一個承諾。
Christofides 演算法是度量 TSP 的 1.5 近似：在任何實例上，它建出的旅程長度最多是最短可能旅程的 1.5 倍。我們能在從不真正算出最短旅程的情況下證明這點——用最小生成樹替 OPT 做下界。
α 為近似比命名；證明把答案對著一個可計算的 OPT 替身去界定。
在近似證明裡你幾乎從不去算 OPT——那正是你在閃躲的難題。訣竅是把你的輸出拿去跟一個「容易算出」的 OPT 界比較，於是即便 OPT 本身仍未知，保證依然可證。