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

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

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

הגדרה

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

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

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

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

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

הערות שוליים


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


שגיאות פרמטריות בתבנית:מיון ויקיפדיה

שימוש בפרמטרים מיושנים [ דרגה ]
סכמת קירוב פולינומית24481441