14אלגוריתמי קירוב ב׳: ½-קירוב חמדני ל-MAXCUT, 2-קירוב ל-TSP המטרי ו-2-קירוב לאריזה למכלים

בקצרה

• זהו השיעור השני על אלגוריתמי קירוב, והוא כולו אלגוריתמים ובניית חסמים — אין בו אף תוצאת קושי. שלושה אלגוריתמים, שלוש הוכחות יחס, ואותה טכניקה בדיוק בכל אחת.
• הטכניקה החוזרת (מ־שיעור 13): האלגוריתם אינו יודע לחשב את $\mathrm{OPT}$. לכן בונים גודל עזר שהאלגוריתם שולט בו, מוכיחים שהוא חוסם את $\mathrm{OPT}$ מהצד הנכון, ומשווים אליו את הפלט. כאן שלושת גדלי העזר הם: $|E|$ עבור $\mathrm{MAXCUT}$, משקל העץ הפורש המינימלי עבור $\mathrm{TSP}$, וסכום האיברים $\sum a_i$ עבור בעיית האריזה.
• ½-קירוב חמדני ל-$\mathrm{MAXCUT}$: מעבר יחיד על הקודקודים לפי סדר; כל קודקוד נכנס לצד שבו יש לו פחות שכנים שכבר הוצבו. ההוכחה מפרקת את $E$ לקבוצות $E_1,\dots,E_n$ לפי הקצה בעל האינדקס הגבוה, ומראה $|F \cap E_j| \ge \tfrac12 |E_j|$ בנפרד לכל $j$. זהו אלגוריתם שונה מהחיפוש המקומי של שיעור 13, ומשיג את אותו יחס — במעבר אחד ובלי איטרציות.
• 2-קירוב לבעיית הסוכן הנוסע כשהמשקלים מטריים: חשב עץ פורש מינימלי $T$, הרץ עליו DFS, והחזר את הקודקודים לפי סדר הגילוי. שלושה אי-שוויונות מרכיבים את ההוכחה: $w(T) \le w(C_{\mathrm{opt}})$, ואז $w(P)=2w(T)$ עבור הסיור שעובר על כל קשת פעמיים, ואז $w(C) \le w(P)$ בזכות אי-שוויון המשולש (״קיצורי דרך״).
• שימו לב לניגוד מול שיעור 13: שם הוכחנו שלבעיית הסוכן הנוסע הכללית אין קירוב ביחס קבוע אלא אם $\mathrm{P}=\mathrm{NP}$. כאן, בתוספת הנחה אחת בלבד — אי-שוויון המשולש — יש קירוב ביחס 2. ההנחה הזו היא כל ההבדל.
• 2-קירוב לבעיית האריזה למכלים (First-Fit): הכנס כל פריט לתא הראשון שהוא נכנס אליו. הלמה המרכזית: בפלט יש לכל היותר תא אחד שסכום איבריו $\le \tfrac12$. מכאן $\sum a_i > \tfrac12(m-1)$, ומכיוון ש-$m_{\mathrm{opt}} \ge \sum a_i$ מקבלים $m \le 2m_{\mathrm{opt}}$.
• שני טריקים כלליים שכדאי לזכור מכאן: חלוקת קבוצת האילוצים לחלקים שהאלגוריתם מכריע עליהם אחד-אחד (הפירוק ל-$E_j$), ומעבר משלמים לחסם — האי-שוויון $m < 2m_{\mathrm{opt}}+1$ הופך ל-$m \le 2m_{\mathrm{opt}}$ רק כי $m$ שלם.

רקע ותלויות

מ־שיעור 13 — הגדרת אלגוריתם הקירוב. נחזור עליה במלואה, כי כל השיעור הזה הוא שלוש הפעלות שלה.

עבור בעיית מינימיזציה ו-$\alpha \ge 1$, אלגוריתם $A$ הוא אלגוריתם קירוב ביחס $\alpha$ אם לכל קלט $I$:

1. $A$ רץ בזמן פולינומי ב-$|I|$;
2. $A(I)$ הוא פתרון אפשרי (feasible) לקלט $I$;
3. $\mathrm{OPT}(I) \;\le\; v(A(I)) \;\le\; \alpha \cdot \mathrm{OPT}(I)$.

עבור בעיית מקסימיזציה ו-$0 < \alpha \le 1$ הכיוון מתהפך: $\alpha \cdot \mathrm{OPT}(I) \;\le\; v(A(I)) \;\le\; \mathrm{OPT}(I).$

בשני המקרים אחד משני אי-השוויונות טריוויאלי (פתרון אפשרי לעולם אינו טוב מהאופטימום), וכל העבודה היא בשני. זו הסיבה שכל שלושת הניתוחים בשיעור בנויים באותו סדר: פיזביליות $\to$ זמן ריצה $\to$ יחס. אל תוותרו על השלב הראשון במבחן; הוא נבדק.

הערה: הסיכום של שיעור 14 כותב ״ביחס קירוב $\tfrac12$״ עבור $\mathrm{MAXCUT}$ ו״ביחס קירוב 2״ עבור שתי בעיות המינימום, כלומר משתמש בקונבנציה שבה $\alpha \le 1$ לבעיות מקסימום ו-$\alpha \ge 1$ לבעיות מינימום. זו הקונבנציה שנשמרת כאן לאורך כל הקובץ. ספרים אחרים כותבים $\mathrm{OPT}/\mathrm{ALG}$ גם לבעיות מקסימום ואז אותו אלגוריתם הוא ״2-קירוב״; שימו לב לכיוון לפני שאתם מצטטים תוצאה.

מ־שיעור 13 — $\mathrm{MAXCUT}$. בהינתן גרף לא מכוון $G=(V,E)$, יש למצוא חלוקה של $V$ לשתי קבוצות כך שמספר הקשתות שקצה אחד שלהן בכל צד יהיה מקסימלי. בשיעור 13 ראינו אלגוריתם חיפוש מקומי: כל עוד יש קודקוד שהעברתו לצד השני מגדילה את החתך — העבר אותו. הוא נותן יחס $\tfrac12$. האלגוריתם של השיעור הזה משיג את אותו יחס בשיטה אחרת לגמרי.

מ־שיעור 13 ומ־שיעור 12 — בעיית הסוכן הנוסע. בשיעור 12 ראינו את הרדוקציה $\mathrm{UHC} \le_p \mathrm{TSP}$ (הזכרה: $A \le_p B$ פירושו ש-$A$ ניתנת לרדוקציה פולינומית ל-$B$, כלומר $B$ קשה לפחות כמו $A$). בשיעור 13 הוכחנו, על גבי אותה רדוקציה, שאם קיים אלגוריתם קירוב ביחס $\alpha$ כלשהו ל-$\mathrm{TSP}$ הכללית אז $\mathrm{P}=\mathrm{NP}$. התוצאה הזו היא הרקע ההכרחי למשפט 3 כאן: היא מסבירה למה מוסיפים את הנחת אי-שוויון המשולש, ולמה בלעדיה אין מה לחפש.

מקורס אלגוריתמים — שני כלים שמשמשים אותנו כקופסה שחורה.

1. עץ פורש מינימלי (MST). לכל גרף לא מכוון קשיר ממושקל אפשר למצוא בזמן פולינומי עץ פורש שמשקלו מינימלי מבין כל העצים הפורשים (Prim ב-$O(|V|^2)$, Kruskal ב-$O(|E| \log |V|)$). התכונה היחידה שנשתמש בה: אם $T$ עץ פורש מינימלי ו-$T'$ עץ פורש כלשהו, אז $w(T) \le w(T')$.
2. DFS. סריקה לעומק של עץ מנוהלת ב-$O(|V|+|E|)$ ומייצרת שני דברים שנצטרך: סדר הגילוי (preorder) של הקודקודים, והסיור הסגור שבו כל קשת של העץ נחצית בדיוק פעמיים — פעם ״ברדת״ ופעם ״בעלייה״.

הגדרות

הגדרה 1: החתך המושרה על ידי קבוצת קודקודים

יהי $G=(V,E)$ גרף לא מכוון, ותהי $U \subseteq V$. החתך המושרה על ידי $U$ הוא $F \;=\; \{\, xy \in E \;:\; x \in U,\; y \in \bar{U} \,\},$ כאשר $\bar{U} = V \setminus U$. ערך הפתרון הוא $|F|$, ובעיית $\mathrm{MAXCUT}$ היא למקסם אותו.

אינטואיציה. צובעים כל קודקוד בשחור או בלבן, וסופרים כמה קשתות מחברות בין צבעים שונים. כל קבוצה $U$ היא פתרון אפשרי — גם $U=\emptyset$ (חתך ריק) וגם $U=V$. אין כאן שום אילוץ פיזביליות מלבד ״$U$ היא תת-קבוצה של $V$״, ולכן הוכחת הפיזביליות של אלגוריתם ל-$\mathrm{MAXCUT}$ היא כמעט טריוויאלית — כל התוכן הוא ביחס.

דוגמה. ב-$K_3$ עם $V=\{v_1,v_2,v_3\}$: עבור $U=\{v_1\}$ מתקבל $F=\{v_1v_2, v_1v_3\}$ ו-$|F|=2$, וזהו האופטימום. אי-דוגמה לרווח: עבור $U=V$ מתקבל $F=\emptyset$ — פתרון אפשרי לחלוטין, וערכו $0$.

הגדרה 2: משקלים המקיימים את אי-שוויון המשולש

יהי $G=(V,E)$ גרף שלם עם משקלים $w: E \to \mathbb{R}^{+}$. נאמר ש-$w$ מקיימת את אי-שוויון המשולש אם לכל $x,y,z \in V$ $w(xz) \;\le\; w(xy) + w(yz).$

אינטואיציה. ״קיצור דרך אינו מייקר״: לעולם לא כדאי לעבור דרך תחנת ביניים כדי להגיע מ-$x$ ל-$z$. כל מרחק גיאומטרי מקיים זאת, וגם מרחקי מסלול קצר בגרף.

דוגמה. ארבע נקודות במישור עם מרחק אוקלידי, למשל קודקודי מלבן $4 \times 3$: המשקלים הם $3,4,5$ והם מקיימים את אי-השוויון. אי-דוגמה: שלושה קודקודים עם $w(xy)=1$, $w(yz)=1$, $w(xz)=5$ — כאן $5 > 1+1$, ולכן משפט 3 אינו חל. זה בדיוק סוג המשקלים שהרדוקציה של שיעור 13 מייצרת, וזו הסיבה שהיא מצליחה לייצר אי-קירוב.

הגדרה 3: בעיית הסוכן הנוסע עם משקלים מטריים

נתון: גרף שלם $G=(V,E)$ עם משקלים $w:E \to \mathbb{R}^{+}$ המקיימים את אי-שוויון המשולש. מטרה: למצוא מעגל המילטוני (מעגל העובר בכל קודקוד של $G$ בדיוק פעם אחת וחוזר לנקודת ההתחלה) שמשקלו מינימלי.

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

אי-דוגמה חשובה. מופע $\mathrm{TSP}$ שבו המשקלים הם $1$ ו-$2$ בשרירותיות אינו בהכרח מטרי, אף שכל מופע כזה שנוצר מהרדוקציה של שיעור 12 כן מקיים את אי-השוויון (כי $1+1 \ge 2$). זו נקודה שכדאי לבדוק לפני שמכריזים שמשפט 3 סותר את שיעור 13 — הוא אינו סותר; שיעור 13 השתמש במשקלים $1$ ו-$\alpha|V|+1$, שאינם מטריים.

הגדרה 4: בעיית האריזה למכלים (Bin Packing)

נתון: מספרים $a_1,\dots,a_n \in (0,1]$. מטרה: לחלק את $a_1,\dots,a_n$ למספר מינימלי של קבוצות, כך שסכום האיברים בכל קבוצה אינו עולה על $1$.

פורמלית, פתרון אפשרי הוא פונקציה $f:[n] \to [m]$ (הקצאת פריט לתא) המקיימת $\sum_{i:\, f(i)=j} a_i \le 1$ לכל $j \in [m]$, וערך הפתרון הוא $m$.

אינטואיציה. $n$ חפצים בגדלים שונים ומכלים בעלי קיבולת $1$ — כמה מכלים צריך. התנאי $a_i \le 1$ הכרחי: פריט גדול מ-$1$ לא היה נכנס לשום תא, ואז לא היה קיים פתרון אפשרי כלל.

דוגמה. $a = (0.4,\,0.7,\,0.3,\,0.6)$: החלוקה $\{a_1,a_4\}$ (סכום $1.0$) ו-$\{a_2,a_3\}$ (סכום $1.0$) היא פתרון אפשרי בעל ערך $2$, וזה האופטימום כי $\sum a_i = 2.0 > 1$. אי-דוגמה. החלוקה $\{a_1,a_2\}$ אינה פתרון אפשרי, כי $0.4+0.7 = 1.1 > 1$.

משפטים והוכחות

משפט 1: אלגוריתם חמדני הוא אלגוריתם קירוב ביחס ½ ל-MAXCUT

האלגוריתם (כפי שהוא בסיכום). לכל גרף $G=(V,E)$, נסמן $V=\{v_1,\dots,v_n\}$.

1. אתחל $U = \bar{U} = \emptyset$.
2. לכל $1 \le i \le n$:
   1. אם ל-$v_i$ יש יותר שכנים ב-$U$ מאשר ב-$\bar{U}$ — הכנס את $v_i$ ל-$\bar{U}$; אחרת הכנס את $v_i$ ל-$U$.
3. החזר את $U$.

שימו לב: בזמן הריצה $U$ ו-$\bar{U}$ הן שתי קבוצות נפרדות שנבנות במקביל, ורק בסוף הריצה מתקיים $\bar{U} = V \setminus U$. הספירה בשלב 2.1 מתייחסת רק לשכנים שכבר הוצבו, כלומר לשכנים $v_k$ עם $k<i$; שכנים עתידיים אינם נמצאים באף אחת מהקבוצות ולכן אינם נספרים.

טענת פיזביליות. האלגוריתם מחזיר תמיד קבוצת קודקודים $U \subseteq V$, וכל תת-קבוצה של $V$ היא פתרון אפשרי לפי הגדרה 1. בנוסף, כל $v_i$ מוכנס בדיוק לאחת משתי הקבוצות בדיוק פעם אחת, ולכן בסוף אכן $U \,\dot\cup\, \bar{U} = V$. $\square$

ניתוח זמן ריצה (כפי שהוא בסיכום). שלב 1 דורש $O(1)$ פעולות. שלב 2 מתבצע ב-$|V|$ איטרציות, ובכל איטרציה עוברים על לא יותר מ-$|E|$ קשתות כדי לספור את השכנים בשני הצדדים. סך הכול $O(|V| \cdot |E|)$, שהוא פולינומי בגודל הקלט. $\square$

הערה: הסיכום מסתפק בחסם הרופף $O(|V|\cdot|E|)$, וזה מספיק לחלוטין למטרה (להראות פולינומיות). לשלמות: אם באיטרציה $i$ סורקים רק את הקשתות הנוגעות ב-$v_i$, כל קשת נסרקת פעמיים לאורך כל הריצה (פעם לכל קצה), והזמן הכולל הוא $O(|V|+|E|)$ — כלומר האלגוריתם הוא ליניארי, במעבר יחיד.

ניתוח יחס הקירוב. יהי $G=(V,E)$ גרף, ונסמן $V=\{v_1,\dots,v_n\}$. יהי $U$ הפלט של האלגוריתם ויהי $F \subseteq E$ החתך המושרה על ידי $U$.

הפירוק המרכזי. לכל $1 \le j \le n$ נסמן ב-$E_j$ את קבוצת הקשתות ש-$v_j$ הוא הקצה שלהן בעל האינדקס הגבוה מבין שני הקצוות: $E_j \;=\; \{\, v_i v_j \in E \;:\; i < j \,\}.$

אינטואיציה (מופיעה בסיכום בכחול): $E_j$ היא קבוצת הקשתות ש-$v_j$ ״יקבע את גורלן״. כשהאלגוריתם מגיע ל-$v_j$, כל הקצוות השניים של קשתות $E_j$ כבר הוצבו, ולכן ההחלטה על $v_j$ קובעת סופית עבור כל קשת ב-$E_j$ אם היא בחתך או לא. הקשתות שיוכרעו מאוחר יותר שייכות ל-$E_k$ עבור $k>j$ ואינן מושפעות.

למה 1.1. $\bigcup_{j=1}^{n} E_j = E$, והקבוצות $E_1,\dots,E_n$ זרות בזוגות; לכן $|E| = \sum_{j=1}^{n} |E_j|$.

הוכחה. תהי $e = v_i v_j \in E$ קשת כלשהי. הגרף פשוט ואין בו לולאות עצמיות, ולכן $i \ne j$, ולקשת יש קצה יחיד בעל אינדקס גבוה יותר — נניח $j > i$. אז $e \in E_j$, ומכאן שהאיחוד הוא כל $E$. מצד שני, $e$ אינה יכולה להשתייך ל-$E_k$ עבור $k \ne j$: לפי ההגדרה, $e \in E_k$ מחייב ש-$v_k$ הוא הקצה בעל האינדקס הגבוה של $e$, וקצה כזה יחיד. לכן הקבוצות זרות בזוגות, והשוויון בגדלים נובע מכלל החיבור. $\square$

(שימו לב ש-$E_1 = \emptyset$ תמיד, כי אין קודקוד עם אינדקס קטן מ-$1$.)

למה 1.2. לכל $1 \le j \le n$ מתקיים $|F \cap E_j| \ge \tfrac12 |E_j|$.

הוכחה. נתבונן ברגע שבו האלגוריתם מטפל ב-$v_j$. נסמן ב-$p$ את מספר השכנים של $v_j$ שכבר נמצאים ב-$U$ וב-$q$ את מספר השכנים שכבר נמצאים ב-$\bar{U}$. כל שכן של $v_j$ בעל אינדקס $i<j$ כבר הוצב (האלגוריתם עובר על האינדקסים בסדר עולה), וכל שכן כזה מגדיר קשת של $E_j$; להפך, כל קשת של $E_j$ מגיעה משכן כזה. לכן $|E_j| = p + q.$

יש שני מקרים, לפי תנאי שלב 2.1:

• אם $p > q$, האלגוריתם מכניס את $v_j$ ל-$\bar{U}$. אז כל אחת מ-$p$ הקשתות אל השכנים שב-$U$ הופכת לקשת חתך, ולכן $|F \cap E_j| \ge p$. מכיוון ש-$p > q$ מתקיים $2p > p+q = |E_j|$, ובפרט $p \ge \tfrac12|E_j|$.
• אחרת $p \le q$, והאלגוריתם מכניס את $v_j$ ל-$U$. אז כל אחת מ-$q$ הקשתות אל השכנים שב-$\bar{U}$ הופכת לקשת חתך, ולכן $|F \cap E_j| \ge q$. מכיוון ש-$q \ge p$ מתקיים $2q \ge p+q = |E_j|$, כלומר $q \ge \tfrac12|E_j|$.

הערה: נקודה עדינה שמותר לפספס בקריאה ראשונה — למה מותר לכתוב ״הופכת לקשת חתך״ בזמן עתיד ולא לחשוש שהחלטה מאוחרת יותר תקלקל אותה? כי שני הקצוות של קשת ב-$E_j$ כבר סופיים ברגע שבו $v_j$ מוצב: קצה אחד הוא $v_j$ עצמו, והשני הוצב קודם. האלגוריתם לעולם אינו מזיז קודקוד שכבר הוצב, ולכן החברות של קשת ב-$F$ נקבעת סופית ברגע ההצבה של הקצה המאוחר יותר. זו בדיוק הסיבה שהפירוק מוגדר לפי האינדקס הגבוה ולא הנמוך. $\square$

סיום ההוכחה. לפי למה 1.1 החתך $F$ מתפרק לפי אותה חלוקה, ולפי למה 1.2: $|F| \;=\; \sum_{j=1}^{n} |F \cap E_j| \;\ge\; \frac12 \sum_{j=1}^{n} |E_j| \;=\; \frac12 |E|.$

מצד שני, כל חתך הוא תת-קבוצה של $E$, ובפרט האופטימלי: $\mathrm{OPT}(G) \le |E|$. לכן $|F| \;\ge\; \frac12 |E| \;\ge\; \frac12 \cdot \mathrm{OPT}(G),$ והאלגוריתם הוא אלגוריתם קירוב ל-$\mathrm{MAXCUT}$ ביחס קירוב $\tfrac12$. $\blacksquare$

הערה: גודל העזר כאן הוא $|E|$ — כמות שהאלגוריתם ״שולט בה״ במובן שהוא סופר אותה חלק-חלק ($E_j$ אחרי $E_j$), והיא חוסמת את $\mathrm{OPT}$ מלמעלה כי הבעיה היא בעיית מקסימום. השוו לשיעור 13: שם, בבעיית המינימום $\mathrm{VC}$, גודל העזר (הזיווג) חסם את $\mathrm{OPT}$ מלמטה. זהו אותו רעיון בשני הכיוונים.

משפט 2: אי-שוויון המשולש המוכלל

יהי $G=(V,E)$ גרף שלם עם משקלים $w:E \to \mathbb{R}^{+}$ המקיימים את אי-שוויון המשולש. אז לכל $v_1,\dots,v_k \in V$ מתקיים $w(v_1,v_k) \;\le\; \sum_{j=1}^{k-1} w(v_j, v_{j+1}).$

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

הערה: ההוכחה הבאה אינה מופיעה בסיכום; היא ההשלמה הסטנדרטית באינדוקציה.

הוכחה. באינדוקציה על $k \ge 2$.

בסיס, $k=2$: הטענה היא $w(v_1,v_2) \le w(v_1,v_2)$ — נכון.

צעד: נניח שהטענה נכונה עבור $k-1$ ($k \ge 3$). לפי אי-שוויון המשולש (הגדרה 2) עם $x=v_1$, $y=v_{k-1}$, $z=v_k$: $w(v_1,v_k) \;\le\; w(v_1,v_{k-1}) + w(v_{k-1},v_k).$ לפי הנחת האינדוקציה על הסדרה $v_1,\dots,v_{k-1}$: $w(v_1,v_{k-1}) \;\le\; \sum_{j=1}^{k-2} w(v_j,v_{j+1}).$ נחבר את שני האי-שוויונות: $w(v_1,v_k) \;\le\; \sum_{j=1}^{k-2} w(v_j,v_{j+1}) + w(v_{k-1},v_k) \;=\; \sum_{j=1}^{k-1} w(v_j,v_{j+1}). \qquad \blacksquare$

הערה טכנית: הקודקודים בסדרה אינם חייבים להיות שונים, וזה חיוני — במשפט 3 נפעיל את הטענה על סיור שחוזר לקודקודים. אם $v_j = v_{j+1}$ מפרשים $w(v_j,v_{j+1})=0$; זה רק מקטין את האגף הימני, כלומר מחזק את הטענה, והבסיס $k=2$ נשאר נכון גם כאשר $v_1=v_2$.

משפט 3: MST + DFS הוא אלגוריתם קירוב ביחס 2 לבעיית הסוכן הנוסע המטרית

האלגוריתם (כפי שהוא בסיכום). לכל קלט $G=(V,E)$, $w:E \to \mathbb{R}^{+}$:

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

טענת פיזביליות. DFS על עץ פורש מגלה כל קודקוד של $V$ בדיוק פעם אחת, ולכן רשימת הגילוי היא תמורה של $V$. הגרף $G$ שלם, ולכן כל שתי תמורות עוקבות מחוברות בקשת, וגם האחרון מחובר לראשון. לכן הרשימה מגדירה מעגל המילטוני — פתרון אפשרי לבעיה. $\square$

ניתוח זמן ריצה. שלב 1 פולינומי (Prim/Kruskal). שלב 2 הוא $O(|V|+|E|)$, ולמעשה $O(|V|)$ כי $T$ עץ ויש בו $|V|-1$ קשתות. שלב 3 דורש רק את הפלט של השלב הקודם. סך הכול פולינומי בגודל הקלט. $\square$

ניתוח יחס הקירוב. יהי $G=(V,E)$ עם $w:E \to \mathbb{R}^{+}$ המקיימת את אי-שוויון המשולש. נסמן ב-$T$ עץ פורש מינימלי של $G$, וב-$C_{\mathrm{opt}}$ את המעגל ההמילטוני בעל המשקל האופטימלי (המינימלי) ב-$G$.

הבחנה 1 (כלשונה בסיכום). נסמן ב-$\hat{T}$ את הגרף המתקבל מ-$C_{\mathrm{opt}}$ על ידי הסרת קשת אחת כלשהי. אז $w(T) \;\le\; w(\hat{T}) \;\le\; w(C_{\mathrm{opt}}).$

הוכחה. אי-השוויון הימני: $\hat{T}$ מתקבל מ-$C_{\mathrm{opt}}$ בהסרת קשת, ומשקל כל קשת אי-שלילי, ולכן ההסרה רק מקטינה את המשקל. אי-השוויון השמאלי: $C_{\mathrm{opt}}$ הוא מעגל העובר בכל קודקוד; הסרת קשת ממעגל משאירה מסלול העובר בכל הקודקודים, ומסלול כזה הוא בפרט עץ פורש של $G$ (קשיר, פורש, ובעל $|V|-1$ קשתות). מכיוון ש-$T$ עץ פורש מינימלי, משקלו קטן או שווה למשקל של כל עץ פורש, ובפרט של $\hat{T}$. $\square$

הבחנה 2. אם נרשום את הקודקודים לפי סדר הביקורים של ה-DFS על $T$ — כלומר את הסיור הסגור המלא, שבו כל קשת של העץ נחצית פעמיים, פעם ״ברדת״ ופעם ״בעלייה״ — נקבל סיור $P$ בגרף המקיים $w(P) = 2\,w(T).$

הוכחה. DFS על עץ, המתחיל בשורש כלשהו $r$ ומסתיים בחזרה ל-$r$, חוצה כל קשת של העץ בדיוק פעמיים: פעם אחת בכיוון מהאב אל הבן ברגע גילוי הבן, ופעם אחת בכיוון ההפוך ברגע שהתת-עץ של הבן הסתיים. מכיוון שאלה כל צעדי הסיור, המשקל הכולל הוא $\sum_{e \in T} 2w(e) = 2w(T)$. $\square$

הערה: הסיכום כותב את שלב 3 של האלגוריתם כ״סדר הגילוי״ ואת הבחנה 2 כ״סדר הביקורים״. אלה שני עצמים שונים ואסור לבלבל ביניהם: סדר הביקורים הוא הסיור $P$ באורך $2(|V|-1)$ צעדים, שבו קודקוד יכול להופיע כמה פעמים; סדר הגילוי (preorder) הוא רשימת ההופעות הראשונות בלבד, שבה כל קודקוד מופיע בדיוק פעם אחת. $P$ אינו פתרון אפשרי לבעיה (הוא חוזר לקודקודים) — הוא רק גודל עזר.

הבחנה 3 (קיצורי הדרך). נסמן ב-$C$ את המעגל המתקבל מרשימת הקודקודים לפי סדר הגילוי — כלומר, מוחקים מ-$P$ את כל ההופעות החוזרות ומשאירים רק את ההופעה הראשונה של כל קודקוד. אז $w(C) \;\le\; w(P).$

הוכחה. נסמן את סדר הגילוי $u_1=r, u_2, \dots, u_n$, ואת הסיור $P$ כרשימת קודקודים $p_0=r, p_1, \dots, p_{2(n-1)}=r$. לכל $t$, נסמן ב-$\pi(t)$ את המיקום ב-$P$ שבו $u_t$ מופיע לראשונה. לפי הגדרת סדר הגילוי, $\pi(1) < \pi(2) < \dots < \pi(n)$.

המעגל $C$ מורכב מ-$n$ קשתות: $u_1u_2, u_2u_3, \dots, u_{n-1}u_n$, ולבסוף $u_nu_1$. לכל $1 \le t \le n-1$, הקטע של $P$ בין המיקום $\pi(t)$ למיקום $\pi(t+1)$ הוא סדרת קודקודים המתחילה ב-$u_t$ ומסתיימת ב-$u_{t+1}$; לפי משפט 2, $w(u_t, u_{t+1}) \;\le\; \sum_{s=\pi(t)}^{\pi(t+1)-1} w(p_s, p_{s+1}).$ באופן דומה, עבור הקשת הסוגרת $u_nu_1$: הקטע של $P$ מהמיקום $\pi(n)$ ועד סוף הסיור מתחיל ב-$u_n$ ומסתיים ב-$p_{2(n-1)}=r=u_1$, ולכן $w(u_n, u_1) \;\le\; \sum_{s=\pi(n)}^{2(n-1)-1} w(p_s, p_{s+1}).$ הקטעים $[\pi(1),\pi(2)], [\pi(2),\pi(3)], \dots, [\pi(n), 2(n-1)]$ הם רצופים, זרים בצעדיהם, ומכסים את כל הסיור מהמיקום $\pi(1)=0$ ועד סופו. לכן סכום האגפים הימניים הוא בדיוק $w(P)$, וסכום האגפים השמאליים הוא בדיוק $w(C)$. $\square$

הערה: בסיכום הבחנה 3 מקוצרת ל״אז מאי-שוויון המשולש $w(C) \le w(P)$״. הפירוט שלמעלה הוא מה שהקיצור הזה מייצג. הנקודה הלא-טריוויאלית היא שהקטעים זרים ומכסים — בלי זה היינו סופרים צעדים של $P$ יותר מפעם אחת ומקבלים חסם חלש יותר.

סיום ההוכחה. נשרשר את שלוש ההבחנות: $w(C) \;\overset{(3)}{\le}\; w(P) \;\overset{(2)}{=}\; 2\,w(T) \;\overset{(1)}{\le}\; 2\,w(C_{\mathrm{opt}}).$ $C$ הוא בדיוק הפלט של האלגוריתם, והוא פתרון אפשרי; לכן האלגוריתם הוא אלגוריתם קירוב ביחס $2$ לבעיית הסוכן הנוסע כשהמשקלים מקיימים את אי-שוויון המשולש. $\blacksquare$

הערה: אי-שוויון המשולש נחוץ רק בהבחנה 3. הבחנות 1 ו-2 נכונות בכל גרף ממושקל אי-שלילי. זו הסיבה שהאלגוריתם עצמו ניתן להרצה על כל מופע $\mathrm{TSP}$ — אבל אין לו שום ערובת יחס בלי ההנחה, ולפי שיעור 13 גם לא יכולה להיות לו כזו אלא אם $\mathrm{P}=\mathrm{NP}$.

משפט 4: First-Fit הוא אלגוריתם קירוב ביחס 2 לבעיית האריזה למכלים

האלגוריתם (כפי שהוא בסיכום). לכל קלט $a_1,\dots,a_n$:

1. לכל $1 \le j \le n$:
   1. הכנס את $a_j$ לקבוצה הראשונה שניתן להכניס אליה את $a_j$; אם אין כזו — פתח קבוצה חדשה.
2. החזר את החלוקה.

טענת פיזביליות. האלגוריתם מכניס כל $a_j$ לקבוצה אחת בדיוק, ולכן הפלט הוא חלוקה של $\{a_1,\dots,a_n\}$ לקבוצות זרות. פריט מוכנס לקבוצה קיימת רק אם הסכום שלה נשאר $\le 1$, ואם נפתחת קבוצה חדשה — סכומה הוא $a_j \le 1$ (כאן נדרש התנאי $a_j \in (0,1]$ מהגדרה 4). לכן כל הקבוצות חוקיות והפלט הוא פתרון אפשרי. $\square$

ניתוח זמן ריצה. באיטרציה $j$ יש לכל היותר $j-1 \le n$ קבוצות פתוחות, וסריקתן לפי הסדר עולה $O(n)$ (החזקת הסכום הנוכחי של כל קבוצה מאפשרת בדיקה ב-$O(1)$ לקבוצה). לכן זמן הריצה הוא $O(n^2)$, פולינומי בגודל הקלט. $\square$

ניתוח יחס הקירוב. יהיו $a_1,\dots,a_n \in (0,1]$. נסמן ב-$m$ את מספר הקבוצות שהחזיר האלגוריתם וב-$f:[n] \to [m]$ את החלוקה שהוא מחזיר. נסמן ב-$m_{\mathrm{opt}}$ את מספר הקבוצות המינימלי האפשרי לקלט הזה, וב-$f_{\mathrm{opt}}:[n] \to [m_{\mathrm{opt}}]$ חלוקה אופטימלית.

למה 4.1 (חסם תחתון על האופטימום). $\displaystyle \sum_{i=1}^{n} a_i \;\le\; m_{\mathrm{opt}}$.

הוכחה. נחלק את הסכום לפי הקבוצות של החלוקה האופטימלית — זו חלוקה של קבוצת האינדקסים, ולכן החלוקה חוקית: $\sum_{i=1}^{n} a_i \;=\; \sum_{j=1}^{m_{\mathrm{opt}}} \; \sum_{i:\, f_{\mathrm{opt}}(i)=j} a_i \;\le\; \sum_{j=1}^{m_{\mathrm{opt}}} 1 \;=\; m_{\mathrm{opt}},$ כאשר אי-השוויון האמצעי הוא בדיוק אילוץ הפיזביליות: הסכום הפנימי הוא סכום האיברים שנכנסו לקבוצה $j$ בחלוקה האופטימלית, והוא חסום על ידי $1$. $\square$

זהו גודל העזר של המשפט: $\sum a_i$ הוא מספר שהאלגוריתם ״רואה״ ישירות, והוא חוסם את $\mathrm{OPT}$ מלמטה — כנדרש בבעיית מינימיזציה.

למה 4.2 (ההבחנה המרכזית). בחלוקה שמחזיר האלגוריתם יש לכל היותר קבוצה אחת שסכום האיברים בה הוא $\le \tfrac12$.

הוכחה. נניח בשלילה שקיימים $1 \le \ell < j \le m$ כך שגם בקבוצה ה-$\ell$ וגם בקבוצה ה-$j$ סכום האיברים (בסוף הריצה) אינו יותר מ-$\tfrac12$.

הקבוצה ה-$j$ נפתחה בשלב כלשהו של הריצה; נסמן ב-$i_0$ את האינדקס של הפריט שבעטיו היא נפתחה, כלומר $a_{i_0}$ הוא הפריט הראשון שהוכנס אליה. מכיוון שסכום כל איברי הקבוצה ה-$j$ בסוף הריצה הוא $\le \tfrac12$, וכל האיברים חיוביים, בפרט $a_{i_0} \;\le\; \tfrac12.$

כעת נתבונן ברגע שבו האלגוריתם טיפל ב-$a_{i_0}$, ונסמן ב-$S_\ell$ את סכום האיברים שהיו בקבוצה ה-$\ell$ באותו רגע. מכיוון ש-$\ell < j$, הקבוצה ה-$\ell$ כבר הייתה פתוחה (הקבוצות נפתחות לפי הסדר), והאלגוריתם בדק אותה לפני שפתח קבוצה חדשה. מכיוון שהאלגוריתם לעולם אינו מוציא איבר מקבוצה, $S_\ell$ קטן או שווה לסכום הסופי של אותה קבוצה, כלומר $S_\ell \le \tfrac12$. לכן $S_\ell + a_{i_0} \;\le\; \tfrac12 + \tfrac12 \;=\; 1,$ כלומר $a_{i_0}$ כן היה נכנס לקבוצה ה-$\ell$, והאלגוריתם היה מכניס אותו אליה במקום לפתוח קבוצה חדשה — בסתירה להנחה ש-$a_{i_0}$ פתח את הקבוצה ה-$j$. $\square$

הערה: בעמוד 4 בסיכום שורת ״סכום האיברים בקבוצה ה-$\ell$ באותו הרגע״ נקראת בקושי וסימן אי-השוויון אינו חד-משמעי. הכיוון היחיד שנותן סתירה הוא $\le \tfrac12$ (כלומר: הקבוצה ה-$\ell$ הייתה ריקה מספיק כדי לקלוט את $a_{i_0}$), וכך נכתב כאן. הכיוון ההפוך היה סותר את הנחת השלילה עצמה ומייתר את הטיעון.

סיום ההוכחה. לפי למה 4.2, לפחות $m-1$ מהקבוצות שהחזיר האלגוריתם הן בעלות סכום גדול ממש מ-$\tfrac12$. לכן, בשילוב עם למה 4.1: $m_{\mathrm{opt}} \;\ge\; \sum_{i=1}^{n} a_i \;=\; \sum_{j=1}^{m} \; \sum_{i:\, f(i)=j} a_i \;>\; \frac12 (m-1).$ (אי-השוויון האחרון חזק ממש: לפחות $m-1$ מהמחוברים גדולים ממש מ-$\tfrac12$, והנותר אי-שלילי. גם במקרה $m=1$ הוא נכון, כי $\sum a_i > 0 = \tfrac12 \cdot 0$.)

מכאן $2m_{\mathrm{opt}} > m-1$, כלומר $m \;<\; 2m_{\mathrm{opt}} + 1.$ וכיוון שמדובר במספרים שלמים, נקבל $m \;\le\; 2m_{\mathrm{opt}}.$ לכן First-Fit הוא אלגוריתם קירוב ביחס $2$ לבעיית האריזה למכלים. $\blacksquare$

הערה: הצעד האחרון הוא הצעד היחיד בשיעור שמשתמש בשלמות. בלעדיו היינו נשארים עם החסם החלש יותר $m \le 2m_{\mathrm{opt}}+1$, שהוא ״קירוב ביחס 2 עד כדי תוספת קבועה״ ולא קירוב ביחס 2. שווה לזכור את התרגיל הזה — הוא חוזר.

הערה (מחוץ לסיכום): ההוכחה מראה שהיחס של First-Fit הוא לכל היותר $2$; היא אינה טוענת שהחסם הדוק. ידוע שהניתוח האסימפטוטי המדויק של First-Fit טוב יותר, וגם ידוע שלבעיית האריזה אין אלגוריתם קירוב ביחס טוב מ-$\tfrac32$ אלא אם $\mathrm{P}=\mathrm{NP}$ (רדוקציה מ-$\mathrm{PARTITION}$: קירוב טוב מ-$\tfrac32$ היה מבחין בין $m_{\mathrm{opt}}=2$ ל-$m_{\mathrm{opt}}=3$). שני הדברים האלה אינם בסיכום ואינם נדרשים למבחן; הם מובאים כאן רק כדי שלא תסיקו מהמשפט שהאלגוריתם ״גרוע פי 2״ בפועל.

דוגמאות ותרגילים מהשיעור

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

הערה: כל הדוגמאות בסעיף זה נבנו כאן, לא בשיעור. הן מכוונות בדיוק לנקודות שההוכחות נשענות עליהן.

דוגמה 1: האלגוריתם החמדני ל-MAXCUT על מעגל באורך 5

יהי $C_5$ עם $V=\{v_1,\dots,v_5\}$ וקשתות $v_1v_2,\; v_2v_3,\; v_3v_4,\; v_4v_5,\; v_5v_1$. הפירוק לפי האינדקס הגבוה: $E_1=\emptyset,\quad E_2=\{v_1v_2\},\quad E_3=\{v_2v_3\},\quad E_4=\{v_3v_4\},\quad E_5=\{v_4v_5,\;v_5v_1\}.$

מעקב אחר הריצה ($p$ = שכנים ב-$U$, $q$ = שכנים ב-$\bar{U}$, בזמן הטיפול):

הפלט: $U=\{v_1,v_3,v_5\}$. החתך המושרה הוא $F=\{v_1v_2,\;v_2v_3,\;v_3v_4,\;v_4v_5\}$, כלומר $|F|=4$ (הקשת $v_5v_1$ אינה בחתך, כי שני קצותיה ב-$U$).

בדיקת הלמות: $|E| = \sum_j |E_j| = 0+1+1+1+2 = 5$ ✓. לכל $j$: $|F \cap E_2|=1 \ge \tfrac12$, $|F \cap E_3|=1 \ge \tfrac12$, $|F \cap E_4|=1 \ge \tfrac12$, ו-$|F \cap E_5|=1 \ge \tfrac12 \cdot 2 = 1$ ✓ — כאן הלמה הדוקה, וזה בדיוק המקרה $p=q$ בצעד 5. סך הכול $|F|=4 \ge \tfrac12 \cdot 5 = 2.5$ ✓.

מהו האופטימום? ב-$C_5$ (מעגל אי-זוגי) אי אפשר לחתוך את כל $5$ הקשתות, כי חתך של גרף לא-דו-צדדי אינו יכול להכיל את כל הקשתות; לכן $\mathrm{OPT}=4$, והאלגוריתם החזיר את האופטימום.

תרגיל. הריצו את אותו אלגוריתם על $K_3$ עם הסדר $v_1,v_2,v_3$. פתרון. $v_1 \to U$; $v_2$: $p=1,q=0 \Rightarrow \bar{U}$; $v_3$: $p=1$ (בגלל $v_1$), $q=1$ (בגלל $v_2$), לא $p>q$, ולכן $v_3 \to U$. מתקבל $U=\{v_1,v_3\}$, $F=\{v_1v_2,v_2v_3\}$, $|F|=2$. גם כאן $\mathrm{OPT}=2$ והבטחת הקירוב $2 \ge \tfrac12 \cdot 3$ מתקיימת בהפרש גדול.

דוגמה 2: MST + DFS על מלבן

$V=\{a,b,c,d\}$ בנקודות $a=(0,0)$, $b=(0,3)$, $c=(4,0)$, $d=(4,3)$ עם מרחקים אוקלידיים — ולכן המשקלים מטריים: $w(ab)=3,\quad w(cd)=3,\quad w(ac)=4,\quad w(bd)=4,\quad w(ad)=5,\quad w(bc)=5.$

שלב 1 — עץ פורש מינימלי. Kruskal לפי סדר עולה: $ab\,(3)$ ✓, $cd\,(3)$ ✓, $ac\,(4)$ ✓ (מחבר את שני הרכיבים), ואז עוצרים עם $3$ קשתות. לכן $T=\{ab,\,cd,\,ac\}$ ו-$w(T)=10$.

שלב 2 — DFS. נתחיל ב-$a$; שכניו ב-$T$ הם $b$ ו-$c$. נניח שמבקרים ב-$b$ ראשון. סדר הביקורים המלא (הסיור $P$): $a \to b \to a \to c \to d \to c \to a,$ ומשקלו $3+3+4+3+3+4 = 20 = 2 \cdot 10 = 2w(T)$ ✓ (הבחנה 2).

שלב 3 — סדר הגילוי. ההופעות הראשונות: $a,\,b,\,c,\,d$. המעגל המוחזר: $C = a \to b \to c \to d \to a, \qquad w(C) = 3+5+3+5 = 16.$ בדיקה: $w(C)=16 \le w(P)=20$ ✓ (קיצור הדרך $b \to c$ החליף את הקטע $b \to a \to c$ שמשקלו $3+4=7$, במחיר $5$).

האופטימום. המעגל $a \to b \to d \to c \to a$ במשקל $3+4+3+4=14$ הוא המינימלי. אכן $16 \le 2 \cdot 14 = 28$ ✓, ובפועל היחס הוא $16/14 \approx 1.14$ — הרבה יותר טוב מהערובה.

בדיקת הבחנה 1: הסרת הקשת $ca$ מ-$C_{\mathrm{opt}}$ נותנת את המסלול $a-b-d-c$ במשקל $10$, ואכן $w(T)=10 \le w(\hat{T})=10 \le w(C_{\mathrm{opt}})=14$ ✓.

תרגיל: כמה חשוב סדר ה-DFS? הריצו שוב עם ביקור ב-$c$ לפני $b$. פתרון. סדר הגילוי הוא $a,c,d,b$, והמעגל המוחזר הוא $a \to c \to d \to b \to a$ במשקל $4+3+4+3=14$ — בדיוק האופטימום. מסקנה: האלגוריתם אינו דטרמיניסטי ביחס לסדר הסריקה, וההוכחה מבטיחה את היחס $2$ עבור כל סדר. אין צורך לבחור סדר ״נכון״.

דוגמה 3: First-Fit על ארבעה פריטים

יהי הקלט $a = (0.4,\; 0.7,\; 0.3,\; 0.6)$.

הפלט: $m=3$ קבוצות — $\{0.4,0.3\},\;\{0.7\},\;\{0.6\}$.

האופטימום. $\{0.4,0.6\}$ (סכום $1.0$) ו-$\{0.7,0.3\}$ (סכום $1.0$) — לכן $m_{\mathrm{opt}}=2$, וזהו מינימום כי $\sum a_i = 2.0 > 1$ מחייב לפחות שתי קבוצות.

בדיקת ההוכחה על הדוגמה. סכומי הקבוצות של האלגוריתם הם $0.7,\,0.7,\,0.6$ — כולם $> \tfrac12$, ולכן ההבחנה של למה 4.2 (״לכל היותר קבוצה אחת עם סכום $\le \tfrac12$״) מתקיימת בשופי. השרשרת: $m_{\mathrm{opt}} = 2 \;\ge\; \sum a_i = 2.0 \;>\; \tfrac12(m-1) = \tfrac12 \cdot 2 = 1 \;\;✓,$ ומכאן $m=3 < 2 \cdot 2 + 1 = 5$, כלומר $m \le 4$ — נכון, אם כי כאן רופף. היחס בפועל הוא $3/2$.

תרגיל: מתי בכל זאת נוצרת קבוצה ״קלה״? פתרון. קחו $a=(0.6,\,0.7,\,0.4)$. First-Fit מחזיר $\{0.6\},\{0.7\},\{0.4\}$, והקבוצה השלישית בעלת סכום $0.4 \le \tfrac12$ — והיא היחידה כזו, וגם האחרונה שנפתחה. זה לא במקרה: הטיעון של למה 4.2 מראה שקבוצה ״קלה״ אינה יכולה להיפתח כאשר כבר קיימת קבוצה ״קלה״ לפניה.

הערות מהשיעור

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

• ההערה הכחולה בעמוד 1: ליד הגדרת $E_j$ רשום ״$E_j$ קבוצת הקשתות ש-$v_j$ יקבע את גורלן״. זו לא הערת נוי — היא ההסבר למה הפירוק חייב להיות לפי האינדקס הגבוה. אם היינו מפרקים לפי האינדקס הנמוך, כשהאלגוריתם היה מטפל ב-$v_j$ עוד לא היה ידוע לאן ילכו הקצוות השניים, ואי אפשר היה להסיק דבר.
• ההערה הכחולה בעמוד 2: ליד הגדרת בעיית הסוכן הנוסע רשום במפורש ״לכל $x,y,z \in V$: $w(xz) \le w(xy)+w(yz)$״ — כלומר, אי-שוויון המשולש הוא חלק מהגדרת הקלט, לא הנחה נוספת שנוסיף בניתוח. מופע שאינו מקיים אותו אינו קלט חוקי לבעיה הזו.
• ההערות הכחולות בעמוד 3: מתחת לשרשרת $w(T) \le w(\hat{T}) \le w(C_{\mathrm{opt}})$ רשומות שתי ההצדקות בנפרד — ״כי $T$ מינימלי״ ו״כי $w$ אי-שלילי״. זכרו ששניהם נדרשים; רבים כותבים במבחן רק את הראשון.
• ההערה הכחולה בעמוד 3, בבעיית האריזה: מתחת לסכום הפנימי רשום ״סכום האיברים שנכנסו לקבוצה $j$״ עם החסם $1$ — כלומר הפיזביליות של האופטימום היא שנותנת את למה 4.1.
• הצלבה עם שיעור 13 — הנקודה שהכי כדאי להבין מהשיעור: בשיעור 13 הוכח שקירוב ביחס קבוע ל-$\mathrm{TSP}$ הכללית שקול ל-$\mathrm{P}=\mathrm{NP}$, וכאן מתקבל קירוב ביחס $2$. אלה אינם סותרים, כי המופעים שהרדוקציה של שיעור 13 בונה (משקל $1$ לקשתות המקוריות ו-$\alpha|V|+1$ לשאר) מפרים את אי-שוויון המשולש בגסות. הנחת המטריות אינה קוסמטית — היא בדיוק מה שמפרק את בניית הקושי.
• הצלבה עם שיעור 13 — שני קירובים ½ ל-$\mathrm{MAXCUT}$: חיפוש מקומי (שיעור 13) ואלגוריתם חמדני חד-מעברי (כאן). שניהם נותנים $|F| \ge \tfrac12|E|$, אבל בדרכים שונות: החיפוש המקומי משתמש בתנאי אופטימליות מקומית וספירה כפולה על הקודקודים, והחמדן משתמש בפירוק ל-$E_j$ וספירה על הקשתות. במבחן שאלה יכולה לבקש כל אחד מהם בשמו; שימו לב מה בדיוק נשאלתם.

פערים בין הסיכום להקלטה

לשיעור הזה אין הקלטה בקורפוס — זו העובדה החשובה ביותר בקובץ הזה, והיא נבדקה ולא הונחה.

• מקור: תמלול 19 (המפגש הקודם). הפער: התמלול נגמר ב-$[01{:}26{:}00]$ בדיוק בסוף עמוד 5 של הסיכום של שיעור 13 — על שקילות $\mathrm{TSP}$ ל-$\mathrm{P}=\mathrm{NP}$ — וחותם ב״שאלות?״. הוא אינו גולש אל החומר של שיעור 14. ההכרעה: אינו נרשם כמקור.
• מקור: תמלול 20 (המפגש הבא). הפער: התמלול הוא כולו אלגוריתמים אקראיים — בעיית המזכיר ואימות כפל מטריצות — ואינו נוגע באלגוריתמי קירוב מלבד אמירה צופה פני עתיד ב-$[00{:}34{:}34]$ (״נשלב אלגוריתמים אקראיים עם אלגוריתמי קירוב״). ההכרעה: אינו נרשם כמקור.
• מקור: הקורפוס בכללותו. הפער: קיים פער אמיתי בהקלטות בין שני המפגשים הללו, כלומר המפגש שהסיכום הזה מתעד מעולם לא הוקלט. ההכרעה: sources.transcripts נשאר רשימה ריקה, confidence נקבע ל-medium, וכל תוכן הקובץ נשען על ארבעת עמודי הסיכום בתוספת השלמה מתמטית סטנדרטית — המסומנת לאורך כל הקובץ ב-> **הערה:**.

מה בדיוק מגיע מהסיכום, ומה הושלם כאן.

• מקור: עמודים 1–4 בסיכום. הפער: — . ההכרעה: מהסיכום, מילה במילה מבחינת התוכן: שלושת האלגוריתמים (החמדני ל-$\mathrm{MAXCUT}$, MST+DFS, First-Fit) על כל שלביהם; הגדרת $E_j$ וההערה הכחולה עליה; טענות $\bigcup E_j = E$, הזרות, ו-$|E|=\sum|E_j|$; אי-השוויון $|F \cap E_j| \ge \tfrac12|E_j|$ והמסקנה $|F| \ge \tfrac12|E|$; ניתוח זמן הריצה $O(|V|\cdot|E|)$; ניסוח אי-שוויון המשולש והצורה המוכללת שלו; הבחנה 1 עם שתי ההצדקות; $w(P)=2w(T)$; $w(C) \le w(P) = 2w(T) \le 2w(C_{\mathrm{opt}})$; הגדרת בעיית האריזה; למה 4.1 על שרשרת הסכומים; למה 4.2 והוכחתה בשלילה; והמעבר $m<2m_{\mathrm{opt}}+1 \Rightarrow m \le 2m_{\mathrm{opt}}$.
• מקור: הסיכום מציג את אי-השוויון המוכלל כ״תזכורת״ בלי הוכחה. הפער: אין הוכחה. ההכרעה: נוספה הוכחה באינדוקציה (משפט 2) המסומנת כהשלמה, כולל הטיפול במקרה $v_j=v_{j+1}$ הנדרש לשימוש בסיור.
• מקור: הסיכום כותב ״אז מאי-שוויון המשולש $w(C) \le w(P)$״. הפער: המעבר מקוצר ואינו מסביר למה קטעי הסיור זרים ומכסים. ההכרעה: הבחנה 3 כתובה כאן במלואה עם מיפוי ההופעות הראשונות $\pi(t)$ וטיעון הכיסוי; מסומן כהשלמה.
• מקור: עמוד 4 בסיכום, בשורה על סכום הקבוצה ה-$\ell$ ״באותו הרגע״. הפער: סימן אי-השוויון אינו קריא באופן חד-משמעי. ההכרעה: נכתב $\le \tfrac12$, שכן זהו הכיוון היחיד שמייצר את הסתירה; צוין ב-open_questions.
• מקור: הסיכום, ניתוח זמן הריצה של האלגוריתם החמדני. הפער: $O(|V| \cdot |E|)$ הוא חסם נכון אך רופף. ההכרעה: נשמר כלשונו כניתוח ״של השיעור״, ונוסף חסם הדוק $O(|V|+|E|)$ בהערה מסומנת — בלי לתקן את הסיכום, כי הוא אינו שגוי.
• מקור: הסיכום אינו מגדיר מחדש ״יחס קירוב״ לבעיית מקסימום. הפער: ההגדרה ניתנה בשיעור 13 לבעיית מינימיזציה בלבד. ההכרעה: ההגדרה למקסימיזציה ($\alpha \le 1$, $v(A(I)) \ge \alpha\,\mathrm{OPT}$) שוחזרה בסעיף הרקע והותאמה לניסוח ״ביחס קירוב $\tfrac12$״ שבעמוד 2.
• מקור: הסיכום. הפער: אין בסיכום אף דוגמה מספרית, אף מופע מפורט ואף תרגיל. ההכרעה: סעיף הדוגמאות כולו נבנה כאן ומסומן ככזה בראשו; כל מופע נבחר כדי לבדוק נקודה ספציפית בהוכחה (הידוק למה 1.2, השפעת סדר ה-DFS, ומקרה שבו First-Fit מפסיד לאופטימום).
• מקור: מחוץ לשני המקורות. הפער: אין בסיכום דיון בהידוק היחס. ההכרעה: נוספה הערה קצרה ומסומנת שמציינת שהיחס $2$ אינו נטען כהדוק ושידועה גם תוצאת אי-קירוב $\tfrac32$ לבעיית האריזה; מודגש שם שזה מחוץ לחומר.
• מקור: קונבנציות הכתיבה של הסדרה. הפער: — . ההכרעה: שמות בעיות ומחלקות נכתבים ב-$\mathrm{}$ ($\mathrm{MAXCUT}$, $\mathrm{TSP}$, $\mathrm{P}$, $\mathrm{NP}$), ואילו שמות המשתנים והאינדקסים ($U,\bar{U},E_j,F,T,\hat{T},P,C,C_{\mathrm{opt}},m,m_{\mathrm{opt}},f,f_{\mathrm{opt}},a_i$) נשמרו בדיוק כפי שהם בסיכום.