אלגוריתמי קירוב

יחסי קירוב ושיטות הוכחה לכיסוי קודקודים, Max-Cut, ‏TSP מטרי ואריזת פריטים.

מטרות

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

1. אופטימיזציה אינה שפת הכרעה

בעיית הכרעה מחזירה ביט יחיד. למשל, VC-DEC שואלת אם לגרף יש כיסוי קודקודים בגודל לכל היותר $k$. בעיית האופטימיזציה MIN-VC מבקשת את הכיסוי הקטן ביותר עצמו, או את גודלו. פורמלית, NP-שלמות היא תכונה של שפת ההכרעה; קירוב הוא הבטחה על ערך פונקציית המטרה.

שאילתות סף קושרות בין השתיים. כאשר ערכי המטרה שלמים וניתנים לייצוג במספר פולינומי של ביטים, אורקל העונה על ״האם $\mathrm{OPT}\le k$?״ מאפשר למצוא את הערך האופטימלי בחיפוש בינארי. לעיתים קרובות שחזור עצמי מוצא גם פתרון. בכיוון ההפוך, אלגוריתם אופטימיזציה מדויק עונה מיד על כל שאלת סף. אבל אלגוריתם קירוב אינו מכריע את השפה המדויקת: אם קירוב פקטור $2$ החזיר עלות $12$, אי־אפשר להסיק אם $\mathrm{OPT}\le7$.

נתאר בעיית אופטימיזציה באמצעות מופע $I$, קבוצת פתרונות ישימים $F(I)$ ופונקציית מטרה $\operatorname{val}(I,S)$. נסמן ב-$\mathrm{OPT}(I)$ את הערך הטוב ביותר. אלגוריתם קירוב חייב קודם כול להחזיר $S\in F(I)$ בזמן פולינומי; רק אחר כך יש משמעות ליחס.

מוסכמות ליחס

במינימיזציה, $\alpha$-קירוב, עבור $\alpha\ge1$, מקיים

במקסימיזציה נשתמש במוסכמת הפקטור הגדול מאחד:

ספרים אחרים מדווחים שבר ביצועים $\rho\in[0,1]$ כך ש-$A(I)\ge\rho\mathrm{OPT}(I)$. לכן ״הבטחת $1/2$״ ו״קירוב פקטור $2$״ עשויים לתאר אותה תוצאה ל-Max-Cut. יש לציין את המוסכמה. ההבטחה היא לכל מופע במקרה הגרוע וכוללת זמן פולינומי; איכות ניסויית ממוצעת בלבד היא היוריסטיקה, לא משפט קירוב.

2. כיסוי קודקודים מינימלי: שידוך מקסימלי

אלגוריתם. מתחילים ב-$C=\varnothing$. כל עוד קיימת צלע לא מכוסה $\{u,v\}$, מוסיפים את שני קצותיה ל-$C$ ומוחקים את כל הצלעות הנוגעות ב-$u$ או ב-$v$. הצלעות שנבחרו יוצרות שידוך מקסימלי $M$.

משפט. האלגוריתם הוא $2$-קירוב ל-Minimum Vertex Cover הלא־ממושקלל.

מהלך ההוכחה.

1. ישימות. בסיום לא נותרה צלע לא מכוסה. באופן שקול, אילו לצלע כלשהי לא היה קצה ב-$C$, ניתן היה להוסיפה ל-$M$, בסתירה למקסימליות.
2. חסם תחתון. כל כיסוי חייב לבחור לפחות קצה אחד מכל צלע ב-$M$. צלעות השידוך זרות בקודקודים, ולכן קודקוד יחיד אינו יכול לכסות שתיים מהן. לכן $\mathrm{OPT}\ge|M|$.
3. חיוב הפתרון. האלגוריתם לוקח בדיוק שני קצוות לכל צלע בשידוך: $|C|=2|M|\le2\mathrm{OPT}$.

במסלול $1-2-3-4$, בחירת $\{1,2\}$ ו-$\{3,4\}$ מחזירה את כל ארבעת הקודקודים, ואילו $\{2,3\}$ הוא כיסוי אופטימלי בגודל שניים. הפקטור הדוק עבור האלגוריתם הזה. ״מקסימלי״ פירושו שאי־אפשר להוסיף צלע; אין פירושו שידוך בגודל מקסימום.

3. Max-Cut: חצי מכל הצלעות

בגרף לא מכוון $G=(V,E)$, ערך החתך $(S,V\setminus S)$ הוא מספר הצלעות החוצות אותו, או משקלן הכולל כאשר המשקלים אי־שליליים.

אלגוריתם אקראי. מציבים כל קודקוד באופן בלתי־תלוי באחד משני הצדדים בהסתברות $1/2$. לכל $e=\{u,v\}$ נגדיר $X_e=1$ אם קצותיה בצדדים שונים. מתקיים $\Pr[X_e=1]=1/2$, ולכן מלינאריות התוחלת

מאחר ש-$\mathrm{OPT}\le|E|$, ערך החתך הצפוי הוא לפחות $\mathrm{OPT}/2$. אין צורך באי־תלות בין המשתנים $X_e$ לצורך סכום התוחלות. חזרות ושמירת החתך הטוב ביותר מגבירות ביטחון, אך טענת התוחלת כבר מוכיחה שקיים חתך כזה.

אפשר לדה־רנדמז. מעבדים קודקודים בזה אחר זה, ובכל שלב בוחרים את הצד שאינו מקטין את התוחלת המותנית של החתך הסופי. שיטת התוחלות המותנות מחזירה חתך בגודל לפחות $|E|/2$. גם שיפור מקומי נותן זאת: כל עוד לקודקוד יש יותר שכנים בצדו מאשר בצד האחר, מעבירים אותו. כל העברה מגדילה ממש ערך שלם, ולכן התהליך נעצר. בסיום לכל קודקוד לפחות חצי מצלעותיו חוצות; סכימת הדרגות החוצות סופרת כל צלע חוצה פעמיים ונותנת $2|\delta(S)|\ge|E|$.

דוגמה. במשולש יש שלוש צלעות והאופטימום הוא שתיים. השמה אקראית נותנת תוחלת $3/2$, ושיפור מקומי מחזיר חתך בגודל שתיים. הניתוח אינו טוען שכל ריצה אקראית חותכת לפחות חצי מהצלעות.

4. ‏TSP מטרי: אלגוריתם העץ הכפול

ב-TSP כללי אין הצדקה לקיצורי דרך. כאן הקלט הוא גרף מלא עם מרחקים אי־שליליים, סימטריים, המקיימים את אי־שוויון המשולש

אלגוריתם.

1. מוצאים עץ פורש מינימלי $T$.
2. מכפילים כל צלע ב-$T$. כעת כל הדרגות זוגיות ולכן קיים מסלול אוילרי סגור.
3. עוברים במסלול האוילרי ומדלגים על קודקודים שכבר בוקרו, עד לחזרה להתחלה.

משפט. העץ הכפול הוא $2$-קירוב ל-TSP מטרי.

מהלך ההוכחה. מוחקים צלע אחת ממסלול המילטוני אופטימלי ומקבלים עץ פורש, ולכן $w(T)\le\mathrm{OPT}$. הכפלת העץ נותנת רב־גרף אוילרי במשקל $2w(T)$. בכל פעם שהמסלול עומד לבקר שוב בקודקודים, מחליפים תת־מסלול בצלע הישירה. אי־שוויון המשולש מבטיח שהקיצור אינו מגדיל עלות. לכן המסלול ההמילטוני המתקבל עולה לכל היותר

דוגמה פתורה. ארבע נקודות בפינות ריבוע יחידה: MST כולל שלוש צלעות באורך אחד, ולכן משקל העץ הכפול הוא $6$. מסלול אוילרי עשוי לחזור לפינה, אך קיצורו יכול לתת את היקף הריבוע בעלות $4$, שהיא אופטימלית. ההבטחה הכללית נשארת $2$ אף שבמופע זה התוצאה טובה יותר.

הטעות העיקרית היא לקצר ללא מטריקה. אם הצלע הישירה יקרה מאוד, החלפת מעקף בן שתי צלעות עלולה דווקא להגדיל עלות.

5. Bin Packing: חסמים אסימפטוטיים ותוספת קבועה

לכל פריט גודל $s_i\in(0,1]$ ולכל סל קיבולת $1$; ממזערים את מספר הסלים. חסם הנפח הוא

אך הוא עשוי להיות חלש מפני שאסור לפצל פריטים.

Next Fit ‏(NF). מחזיקים סל פתוח אחד. אם הפריט הבא נכנס, אורזים אותו; אחרת סוגרים את הסל ופותחים חדש. אם NF השתמש ב-$m$ סלים, העומס הכולל בכל זוג סלים עוקבים גדול מ-$1$: הפריט הראשון בסל המאוחר לא נכנס לקודם. מזווגים סלים ומקבלים

ולכן $m\le2\mathrm{OPT}$; ניסוח חד יותר הוא $m<2\mathrm{OPT}+1$. זהו אלגוריתם מקוון שאינו רואה את העתיד.

First Fit Decreasing ‏(FFD). ממיינים את הפריטים בסדר לא־עולה ואז מכניסים כל פריט לסל הראשון שבו יש מקום. משפט קלאסי חזק יותר קובע

זהו חסם מוחלט עם קבוע חיבור, שממנו נובע יחס אסימפטוטי $11/9$. אסור למחוק את הקבוע כאשר $\mathrm{OPT}$ קטן. ההוכחה המלאה ממיינת פריטים למחלקות גדלים ומעבר להיקף השיעור; עמודי סיכום הקורס תומכים בהצגת האלגוריתם, והמסגרת הפורמלית נבדקה בספרי הלימוד.

לדוגמה, הפריטים $0.6,0.6,0.4,0.4$ נכנסים לשני סלים מושלמים אם האלגוריתם משדך גדול עם קטן. בסדרים ארוכים יותר NF רגיש מאוד לסדר, ולכן המיון המוקדם של FFD משמעותי.

6. תבנית הוכחה לשימוש חוזר

לכל טענת קירוב:

1. מציינים את הנחות הקלט ואת פונקציית המטרה.
2. נותנים אלגוריתם בר־ביצוע בזמן פולינומי.
3. מוכיחים שהפלט ישים.
4. מוצאים חסם תחתון על $\mathrm{OPT}$ במינימיזציה או חסם עליון במקסימיזציה.
5. קושרים את ערך הפלט לחסם.
6. מציינים אם ההבטחה דטרמיניסטית, בתוחלת, בהסתברות גבוהה, מוחלטת או אסימפטוטית.

גודל שידוך חוסם את כיסוי הקודקודים מלמטה; מספר הצלעות חוסם Max-Cut מלמעלה; משקל MST חוסם TSP מטרי מלמטה; והנפח הכולל חוסם את מספר הסלים מלמטה.

טעויות נפוצות

• לכנות בעיית אופטימיזציה ״NP-שלמה״ בלי לציין את גרסת ההכרעה.
• לחסום עלות בלי להוכיח ישימות וזמן פולינומי.
• להפוך את אי־השוויון בין מינימיזציה למקסימיזציה.
• להסיק מתוחלת הבטחה לכל ריצה אקראית.
• לקצר מסלול TSP בלי אי־שוויון המשולש.
• להציג יחס Bin Packing אסימפטוטי כחסם מדויק לכל מופע.

המחשות

על הלוח אפשר לצייר ארבעה ״גשרי הוכחה״: שידוך אל חסם VC; כל הצלעות אל חסם Max-Cut; מסלול אופטימלי פחות צלע אל MST; ונפח כולל אל מספר סלים. על כל גשר מסמנים את כיוון אי־השוויון.

תרגילים

תרגיל 1 — פקטור מחסם

אלגוריתם מינימיזציה החזיר ערך $30$, והוכחתם $\mathrm{OPT}\ge20$. איזה פקטור קירוב הוכחתם? הסבירו מדוע אין צורך לדעת את $\mathrm{OPT}$ המדויק.

תרגיל 2 — Vertex Cover משידוך מקסימלי

הוכיחו שאלגוריתם הכיסוי משני קצות צלעות שידוך מקסימלי הוא $2$-קירוב. הבחינו בין שידוך מקסימלי לשידוך מקסימום.

תרגיל 3 — Max-Cut ותוחלת

הוכיחו $\mathbb E[X]\ge\tfrac12\sum_e w_e$ לחלוקה אקראית מאוזנת עם משקלים אי־שליליים, גם בתלות בין צלעות. מתי משקלים שליליים שוברים את הטיעון?

תרגיל 4 — TSP מטרי

סכמו הוכחת $2$-קירוב לעץ הכפול תחת אי־שוויון המשולש. מה נשבר בלי המשולש?

תרגיל 5 — Bin Packing ונפח

‏NF השתמש ב-$9$ סלים. מה נותן טיעון זוגות הסלים על $\mathrm{OPT}$? מדוע יחס אסימפטוטי $11/9$ אינו מחליף תוספת קבועה במופעים קטנים?

סיכום

קירוב הוא משפט מקרה־גרוע: פתרון ישים בזמן פולינומי מול חסם על $\mathrm{OPT}$. כיוון החסם והנחות הבעיה הם חלק מההוכחה.

תרגול מודרך

משימה 1 — כיוון החסם

ריצת VC בחרה $6$ צלעות שידוך ($12$ קודקודים). מצאתם גם כיסוי ידני בגודל $8$. מה כל מספר מוכיח לגבי הפקטור?

משימה 2 — תוחלת מול דטרמיניזציה

ב-Max-Cut האקראי ייתכן חתך ריק בריצה בודדת. כיצד שיטת התוחלות המותנות הופכת הבטחת תוחלת לאלגוריתם דטרמיניסטי?

משימה 3 — קירוב מול NP-שלמות

מדוע אלגוריתם קירוב פולינומי לבעיית אופטימיזציה אינו סותר NP-שלמות של גרסת ההכרעה?

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

• ראיות מן הסיכום הסטודנטיאלי (היקף בלבד): סיכומי שיעור/סיכום ממוזג.pdf, עמ׳ 58–63, 67 ו-76–80. עמ׳ 79–80 עוסקים ב-Steiner Tree ומשתמשים בתבנית קשורה של MST, הכפלה וקיצור; הם אינם מציגים במפורש TSP מטרי. לכן שיעור ה-TSP המטרי לעיל נתמך בספרי הלימוד ואינו מיוחס לסיכום הממוזג. הסיכום הוא ראיה לדגשי הקורס, לא סמכות סופית.
• סמכות ספרי לימוד: Sipser, Introduction to the Theory of Computation, מהדורה 3, §10.1, עמ׳ 393–396 (מסגרת הקירוב); Papadimitriou, Computational Complexity, פרק 13, בפרט §13.1, עמ׳ 299–309 (אלגוריתמי קירוב) ו-§13.2, עמ׳ 309–319 (הקשר סיבוכיותי).
• מצב עריכתי: ההגדרות וארבעת הניתוחים נבדקו מול הסעיפים האלה. קבוע FFD מובא כעובדת סקר קלאסית ואינו מוכח כאן. נבדק; ביטחון גבוה.