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

(הופנה מהדף PTAS)

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

הגדרה

עריכה

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

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

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

עריכה

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

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

עריכה

הערות שוליים

עריכה