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

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

הגדרה

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

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

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

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

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

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

הערות שוליים

^ Katherine Lai,The Knapsack Problem and Fully Polynomial Time Approximation Schemes (FPTAS)2006

[1] Katherine Lai,The Knapsack Problem and Fully Polynomial Time Approximation Schemes (FPTAS)2006

[1]