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

מתוך ויקיפדיה, האנציקלופדיה החופשית
(הופנה מהדף PTAS)
קפיצה לניווט קפיצה לחיפוש

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

הגדרה[עריכת קוד מקור | עריכה]

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

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

סכמת קירוב פולינומית מלאה[עריכת קוד מקור | עריכה]

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

קישורים חיצוניים[עריכת קוד מקור | עריכה]

הערות שוליים[עריכת קוד מקור | עריכה]