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

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

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

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

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

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

הערות שוליים

קטגוריה:מחלקות סיבוכיות