סכמת קירוב פולינומית – הבדלי גרסאות

תת קבוצה ממש (אלא אם כן P=NP) של אלגוריתמים אלו היא סכמת קירוב פולינומית מלאה ('''FPTAS'''). באלגוריתמים אלו הסיבוכיות פולינומית גם בגודל הקלט וגם ב-<math>1/\varepsilon</math>. קירוב כזה קייםלדוגמה, ל[[בעיית תרמיל הגב]] למשליש אלגוריתם שכזה{{הערה|Katherine Lai,[http://math.mit.edu/~goemans/18434S06/knapsack-katherine.pdf The Knapsack Problem and Fully Polynomial Time Approximation Schemes (FPTAS)]2006}}.