רדוקציה מחלוקה לאריזת פחים ואיתור מחסום ה־3/2

מיפוי שאלת חלוקה שווה לפחים בקיבולת S/2, כליאת האופטימום בין 2 ל־3, וקריאת קבוע אי־הקירוב המוחלט.

שאלה

הקלט לבעיית אריזת הפחים (BIN-PACKING) הוא פריטים $a_1,\ldots,a_m$ וקיבולת פח $B$, והמבוקש הוא המספר הקטן ביותר של פחים בקיבולת $B$ שמכילים את כל הפריטים. בצעו רדוקציה מ־PARTITION אל הבעיה הזו בעזרת $B=S/2$ כאשר $S=\sum_i a_i$, הוכיחו שהמופעים הנוצרים הם תמיד בעלי אופטימום $2$ או $3$, והסיקו שאף אלגוריתם פולינומי אינו משיג יחס קירוב מוחלט קטן מ־$3/2$ אלא אם $\mathrm{P}=\mathrm{NP}$. נסחו במדויק על איזה יחס המחסום חל.

דרישות קדם

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

רמז 1

בקיבולת $S/2$ שני הפחים של אריזה חוקית בשני פחים מלאים עד הסוף, בלי שום מקום פנוי.

רמז 2

באריזת First-Fit, כל שני פחים יחד מכילים יותר מ־$B$.

רמז 3

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

פתרון מלא

הרדוקציה. בהינתן רב־קבוצה $A=\{a_1,\ldots,a_m\}$ של מספרים שלמים חיוביים עם $S=\sum_i a_i$, מטפלים תחילה בשני מקרי קצה. אם $S$ אי־זוגי אין חלוקה שווה, ואם קיים $a_i>S/2$ הפריט הזה אינו יכול להיכלל בחלק שסכומו $S/2$; בשני המקרים מחזירים מופע "לא" קבוע. אחרת מחזירים את מופע האריזה עם אותם פריטים, קיבולת $B=S/2$ ותקציב של $k=2$ פחים. חישוב $S$ והשוואתו לכל $a_i$ דורשים מספר פולינומי של פעולות בינאריות, ואף מספר אינו גדל, ולכן המיפוי פולינומי.

נכונות. סכום הפריטים הוא $S=2B$. אם $A$ מתחלקת לשני חלקים שסכום כל אחד $S/2$, כל חלק הוא בדיוק פח מלא, ולכן שני פחים מספיקים. להפך, אם שני פחים בקיבולת $B$ מכילים פריטים שסכומם $2B$, אף פח אינו יכול לשאת פחות מ־$B$ בלי לדחוף את השני מעל $B$, ולכן כל אחד נושא בדיוק $B$ ושני הפחים מציגים חלוקה שווה. לכן

הפער. בכל מופע שהרדוקציה מייצרת האופטימום נמצא בקבוצה $\{2,3\}$.

חסם תחתון: סכום הפריטים הוא $2B>B$, ולכן פח אחד לעולם אינו מספיק ומתקיים $\mathrm{OPT}\ge2$, עם שוויון בדיוק כאשר קיימת חלוקה.

חסם עליון: מריצים First-Fit. נקבע שני פחים $i<j$ בפלט שלו, ויהי $x$ הפריט הראשון שהוכנס לפח $j$. ברגע שהוכנס $x$, פח $i$ כבר היה קיים ו־$x$ לא נכנס אליו, ולכן תכולת פח $i$ באותו רגע ועוד $x$ עלו על $B$. תכולה לעולם אינה קטנה, ולכן העומסים הסופיים מקיימים $\mathrm{load}(i)+\mathrm{load}(j)>B$. אילו First-Fit היה משתמש בארבעה פחים או יותר, זיווג $(1,2)$ ו־$(3,4)$ היה נותן עומס כולל גדול מ־$2B$, בסתירה לכך שסכום הפריטים הוא בדיוק $2B$. לכן First-Fit משתמש בשלושה פחים לכל היותר ומתקיים $\mathrm{OPT}\le3$.

המחסום. נניח שקיים אלגוריתם פולינומי $\mathcal{A}$ בעל יחס קירוב מוחלט $\rho<3/2$, כלומר הוא מחזיר לכל היותר $\rho\cdot\mathrm{OPT}$ פחים בכל מופע. נריץ אותו על מופע שנוצר מ־PARTITION. אם $\mathrm{OPT}=2$ אז $\mathcal{A}$ מחזיר לכל היותר $2\rho<3$ פחים; מספרי פחים הם שלמים ואף אלגוריתם אינו טוב מהאופטימום, ולכן הוא מחזיר בדיוק $2$. אם $\mathrm{OPT}=3$ אז $\mathcal{A}$ מחזיר לפחות $3$. קריאת מספר הפחים המוחזר מכריעה אפוא את PARTITION בזמן פולינומי, ו־PARTITION היא NP-שלמה, ולכן $\mathrm{P}=\mathrm{NP}$. בניסוח נגדי: אלא אם $\mathrm{P}=\mathrm{NP}$, לאף אלגוריתם פולינומי אין יחס מוחלט קטן מ־$3/2$.

זוג מופעים מחושב. ניקח $A'=\{3,5,6,11,39,36\}$, הרב־קבוצה שמייצרת הרדוקציה מ־Subset Sum ל־Partition. כאן $S=100$, $B=50$, והקבוצות $\{36,3,11\}$ ו־$\{39,5,6\}$ מסתכמות שתיהן ל־$50$, ולכן $\mathrm{OPT}=2$. נשנה פריט אחד, $11\mapsto13$, ונקבל $A''=\{3,5,6,13,39,36\}$ עם $S=102$ ו־$B=51$, שבו אין כלל תת־קבוצה שסכומה $51$; חיפוש ממצה על כל השמות ששת הפריטים לפחים מאשר $\mathrm{OPT}=3$. First-Fit בסדר הכתוב מחזיר עומסים $27,39,36$ שסכומי הזוגות שלהם הם $66,63,75$, כולם מעל $51$ — בדיוק תכונת הזוגות שאוסרת פח רביעי.

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

• First-Fit משתמש בלכל היותר $2\cdot\mathrm{OPT}$ פחים, משום ששני פחים מלאים עד חצי לכל היותר היו סותרים את תכונת הזוגות, ולכן לכל היותר פח אחד ריק בחציו. היחס האסימפטוטי ההדוק שלו הוא $1.7$. הוא אינו הליך הכרעה: על $A'$ בסדר הכתוב הוא פותח שלושה פחים אף ש־$\mathrm{OPT}=2$.
• First-Fit-Decreasing מקיים $\mathrm{FFD}\le\frac{11}{9}\mathrm{OPT}+\frac69$, והיחס המוחלט שלו הוא בדיוק $3/2$. הוא נוגע במחסום ואינו חוצה אותו. על $A'$ הוא אכן מוצא את האריזה האופטימלית $\{39,11\}$ ו־$\{36,6,5,3\}$.
• קיימת סכמת קירוב אסימפטוטית: לכל $\varepsilon>0$ יש אלגוריתם פולינומי שאורז ב־$(1+\varepsilon)\mathrm{OPT}+O(1)$ פחים. אלגוריתם קרמרקר–קארפ אורז ב־$\mathrm{OPT}+O(\log^2 \mathrm{OPT})$ פחים.

אף אחת מההבטחות האסימפטוטיות אינה סותרת את מחסום ה־$3/2$, משום ששתיהן מתירות איבר חיבורי ששולט דווקא על המופעים הזעירים שהרדוקציה מייצרת, שבהם $\mathrm{OPT}\in\{2,3\}$. המשפט "אי אפשר לקרב אריזת פחים מתחת ל־$3/2$" בלי המילה מוחלט הוא אפוא שגוי.

נקודות בדיקה

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

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

• הסקה שאריזת פחים אינה ניתנת לקירוב מתחת ל־$3/2$ גם במובן האסימפטוטי; סכמת הקירוב האסימפטוטית וקרמרקר–קארפ מפריכות את הקריאה הזו.
• שכחת התנאי $a_i>S/2$, שמותיר פריט שאינו נכנס לשום פח.
• שימוש ב־$\mathrm{OPT}\ge2$ בלבד בלי להוכיח $\mathrm{OPT}\le3$, שהוא מה שהופך את הפער לדו־ערכי.
• התייחסות ל־First-Fit כאל הליך הכרעה ל־PARTITION משום שהוא מקיים $2\cdot\mathrm{OPT}$.

מקורות ואימות

• Garey-Johnson, SR1 (bin packing)
• Lecture 9 First-Fit questions in data/canonical_questions.json
• הערת כיסוי הקורפוס: שיעור 9 שואל ישירות על First-Fit לאריזת פחים (CQ-0199, CQ-0211, CQ-0212, CQ-0224); מחסום ה־$3/2$ עצמו הוא חומר ספרי לימוד ואינו מופיע בסיכום הממוזג.
• מיפוי קטלוג: data/exercises.json; הניסוח והפתרון עצמאיים; הגשות אישיות אינן מקור סמכות.

הערת מקור וביטחון

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

פתיחה בגלריית ההמחשות: חלוקה → אריזת פחים ומחסום ה־3/2