近似演算法（approximation algorithm）
假設你面對的精確問題是 NP 困難的，因此沒有已知的高效演算法能命中完美答案。你並不總是有放棄的餘裕。一個自然的折衷是：要求一個可被證明接近最佳、而且能快速算出的答案。近似演算法正是如此：一個快速（多項式時間）的演算法，它不保證給出最佳解，卻保證給出一個與最佳解相差在某個有保證倍數之內的解。
關鍵想法是近似比。對最小化問題，若一個演算法在每個輸入上輸出的成本至多是真實最佳值的 c 倍，它就是一個 c-近似（所以 c 是像 2 這樣的數，意指「絕不超過最佳可能的兩倍貴」）。對最大化問題，它保證至少達到最佳值的 1/c。關鍵是：即使演算法從不計算真實最佳值、甚至可能根本不知道它，這個保證仍然成立——近似比靠巧妙的推理證明，常是把輸出與一個你能算出的下界相比。有些問題甚至允許 PTAS（多項式時間近似方案）：對你想要的任何精度 1+epsilon，都存在一個達成它的多項式時間演算法，以更多時間換取更緊的保證。
近似是面對 NP 困難的主要誠實回應之一——一種「應付」而非「征服」的方式（見「應付 NP 完全」）。它在實務上至關重要：包裹路由、排程、網路設計與分群全都仰賴有證明保證的近似，而非把賭注押在啟發式上。但保證因問題而天差地遠。頂點覆蓋有簡單的 2-近似；度量型 TSP 有 1.5-近似；而正如下一條目所解釋，有些問題被證明連近似到某個比率以上都很難，所以「近似一下就好」並非總是出路。
對頂點覆蓋，一條微小的貪心規則就給出 2-近似：反覆挑任一條尚未被覆蓋的邊，把它的兩個端點都加入覆蓋集。每條被選的邊在最佳覆蓋裡至少要有一個端點，而這些被選的邊彼此不共用頂點，所以最佳值至少是你所取頂點數的一半——你的覆蓋集至多是最佳的兩倍，有保證，而你根本不知道真實最佳值是多少。
2-近似的解絕不超過最佳值的兩倍，這是靠與一個可計算的界比較證明的。
近似比是最壞情況的保證，不是典型表現；2-近似在實務上常表現得好得多。而這個保證是證明而非期望——一個「通常看起來不錯」卻沒有已證界的啟發式，在這個技術意義下並不算近似演算法。