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

סכמת קירוב פולינומית (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 - שיטות ליצירת אלגוריתמי קירוב פולינומיים.

הערות שוליים

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

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