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

מתוך המכלול, האנציקלופדיה היהודית
קפיצה לניווט קפיצה לחיפוש

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

הגדרה

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

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

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

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

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

הערות שוליים


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