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

בעייה נמצאת במחלקת PTAS אם ורק אם קיים אלגוריתם קירוב שמקבל <math>\varepsilon</math> כלשהו וקלט לבעיה, כאשר <math>OPT</math> הוא הפתרון האופטימלי עבור קלט זה, ומחזיר תשובה שהיא לפחות <math>(1-\varepsilon)*OPT</math> עבור בעיית מכסימוםמקסימום או לא יותר מ <math>(1+\varepsilon)*OPT</math> עבור בעיית מינימום, בסיבוכיות פולינומית לגודל הקלט ובהתייחס ל<math>\varepsilon</math> כקבוע, מה שמאפשר שהאלגוריתם יהיה אקספוננציאלי ביחס ל<math>1/\varepsilon</math>.