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

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

הגדרה

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

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

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

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

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

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