סכמת קירוב פולינומית

סכמת קירוב פולינומית (PTAS) היא מחלקת סיבוכיות של בעיות אופטימיזציה להן ניתן למצוא פתרון מקורב ככל שנרצה על ידי אלגוריתם קירוב בסיבוכיות פולינומית לגודל הקלט בהתייחס ל-$\epsilon$ כקבוע.

הגדרה

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

מחלקה זאת היא תת-קבוצה ממש של מחלקת הסיבוכיות APX שמאגדת את כל הבעיות שקיים להם אלגוריתם קירוב פולינומי, אלא אם כן P=NP מה שיגרור זהות בין הקבוצות.

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

תת קבוצה ממש (אלא אם כן P=NP) של אלגוריתמים אלו היא סכמת קירוב פולינומית מלאה (FPTAS). באלגוריתמים אלו הסיבוכיות פולינומית גם בגודל הקלט וגם ב-$1/\epsilon$. לדוגמה, לבעיית תרמיל הגב יש אלגוריתם שכזה.

קישורים חיצוניים

• Approximation Schemes – A Tutorial - שיטות ליצירת אלגוריתמי קירוב פולינומיים.