多項式時間逼近演算法

多項式時間逼近演算法

我們可以找到一些 0-1 揹包問題或子集和問題等 NP 完全問題的多項式時間解決方案。這些問題在現實世界中十分常見，因此必須有一些方法來處理這些問題。

多項式時間逼近演算法（PTAS）是一種用於逼近最佳化問題的演算法。對於 0-1 揹包問題，有一個偽多項式解決方案，但當值很大時，該解決方案不可行。所以我們需要一種 PTAS 解決方案。

一些 NP 完全問題，如圖著色、K 中心問題等，它們沒有已知的多項式時間解決方案。PTAS 用於逼近演算法。這些演算法取引數 ε> 0，為了逼近，我們將最小化 (1 + ε) 並最大化 (1 - ε)。

示例

例如，如果我們選擇一個最小化問題並取 ε = 0.5，那麼使用 PTAS 找到的解接近 1.5。所以執行時間必須是關於 n 的多項式，但它可以是關於 ε 的指數。

薩穆爾·薩姆

更新於： 2020-06-17

837 次瀏覽

提升你的 職業

完成課程，獲得認證

開始吧