PARTITION ≤p BIN-PACKING | Complexity Atlas

הבנייה

הרעיון: נרמול לפי חצי הסכום. קלט של $\mathrm{BIN\text{-}PACKING}$ הוא מספרים בקטע $(0,1]$ ומספר תאים $k$ , והשאלה היא אם אפשר לחלק אותם ל- $k$ תאים שבכל אחד הסכום $\le1$ . אם נחלק כל $a_i$ בחצי הסכום, סכום כל המספרים יהיה בדיוק $2$ , ואז חלוקה לשני תאים בקיבולת $1$ אפשרית אם ורק אם יש חלוקה שווה.

המכשול: ייתכן $a_i$ ענק שאחרי הנרמול יעלה על $1$ — פלט לא חוקי. אבל אם $2a_i>T$ אז אין בכלל חלוקה שווה, ולכן אפשר להחזיר במקרה זה מחרוזת קבועה שאיננה בשפה.

אלגוריתם $R'$ . על קלט $(a_1,\dots,a_n)$ , מספרים טבעיים (בלי הגבלת הכלליות $a_i>0$ ; אפסים אפשר להשמיט מבלי לשנות את התשובה):

חשב $T\leftarrow\sum_j a_j$ .
אם קיים $i$ כך ש- $2a_i>T$ : החזר $\left(\tfrac34,\tfrac34,\tfrac34,\,2\right)$ .
אחרת, לכל $i$ הגדר $b_i\leftarrow\dfrac{2a_i}{\sum_j a_j}$ , והחזר $(b_1,\dots,b_n,\,2)$ .

התכונה המרכזית של הפלט. בשלב 3, $\sum_{i=1}^{n}b_i=\sum_i\frac{2a_i}{T}=\frac{2}{T}\sum_i a_i=\frac{2}{T}\cdot T=2 ,$ כאשר הוצאת $\frac2T$ מחוץ לסכום מותרת כי הוא קבוע ואינו תלוי ב- $i$ . כמו כן $b_i>0$ ו- $b_i\le1$ (כי $2a_i\le T$ בשלב זה), ולכן $b_i\in(0,1]$ והפלט חוקי.

על הייצוג. ה- $b_i$ רציונליים ומיוצגים כזוג שלמים — מונה $2a_i$ ומכנה $T$ — ואורך כל אחד $O(m+\log n)$ . אין דרישה שקלט $\mathrm{BIN\text{-}PACKING}$ יהיה שלם; ההגדרה מדברת על מספרים בקטע $(0,1]$ .

המחשה

A′ = {3, 5, 6, 11, 39, 36}S = 100

מלבן פריט, גובהו פרופורציוני לערכו

נכונות — שני הכיוונים

PARTITION ∈ ⟹ BIN-PACKING ∈

נניח $(a_1,\dots,a_n)\in\mathrm{PARTITION}$ ; קיימת $I$ עם $\sum_{i\in I}a_i=\sum_{i\notin I}a_i=T/2$ .

האלגוריתם הגיע לשלב 3. נניח בשלילה שהוא נעצר בשלב 2, כלומר קיים $i_0$ עם $2a_{i_0}>T$ . הצד המכיל את $a_{i_0}$ סוכם ללפחות $a_{i_0}>T/2$ — בסתירה לכך ששני הצדדים סוכמים ל- $T/2$ בדיוק. לכן האלגוריתם אכן הגיע לשלב 3.

האריזה. נשים את $\{b_i\}_{i\in I}$ בתא הראשון ואת $\{b_i\}_{i\notin I}$ בשני. סכום התא הראשון הוא $\sum_{i\in I}b_i=\frac{2}{T}\sum_{i\in I}a_i=\frac{2}{T}\cdot\frac{T}{2}=1\;\le\;1 ,$ ובאותו חשבון גם השני. שני התאים מקיימים את הקיבולת, והשתמשנו ב- $2$ תאים בדיוק. לכן $(b_1,\dots,b_n,2)\in\mathrm{BIN\text{-}PACKING}$ .

BIN-PACKING ∈ ⟹ PARTITION ∈

נניח שהפלט ב- $\mathrm{BIN\text{-}PACKING}$ .

מקרה 1: האלגוריתם עצר בשלב 2. אז הפלט הוא $\left(\tfrac34,\tfrac34,\tfrac34,2\right)$ . שלושה פריטים בגודל $\tfrac34$ אינם נכנסים לשני תאים בקיבולת $1$ : כל תא יכול להכיל לכל היותר פריט אחד (שכן $\tfrac34+\tfrac34=\tfrac32>1$ ), ולכן דרושים לפחות $3$ תאים. אז הפלט אינו ב- $\mathrm{BIN\text{-}PACKING}$ — סתירה להנחה. לכן מקרה זה אינו יכול להתרחש, והאלגוריתם הגיע לשלב 3.

מקרה 2: האלגוריתם הגיע לשלב 3. אז קיימת אריזה של $b_1,\dots,b_n$ לשני תאים, כל אחד בסכום $\le1$ . נסמן ב- $I$ את קבוצת האינדקסים שנארזו בתא הראשון. אז $\sum_{i\in I}b_i\le1\qquad\text{וגם}\qquad\sum_{i\notin I}b_i\le1 .$ אבל סכום כל ה- $b_i$ הוא בדיוק $2$ , ולכן $\sum_{i\in I}b_i=2-\sum_{i\notin I}b_i\;\ge\;2-1=1 .$ משתי אי-השוויונות $\sum_{i\in I}b_i=1$ בדיוק, ובאותו חשבון גם $\sum_{i\notin I}b_i=1$ .

נתרגם חזרה: $\sum_{i\in I}\frac{2a_i}{T}=1$ , כלומר $\sum_{i\in I}a_i=\frac{T}{2}$ , ולכן גם $\sum_{i\notin I}a_i=T-\frac T2=\frac T2$ . שני הצדדים שווים, ומכאן $(a_1,\dots,a_n)\in\mathrm{PARTITION}$ .

סיבוכיות הרדוקציה

זמןO(|x|²)

מקוםO(|x|)

גודל הפלטO(|x|)

חישוב $T$ עולה $O(n(m+\log n))$ ; שלב 2 הוא $n$ השוואות; שלב 3 הוא $n$ פעולות של כתיבת הזוג $(2a_i,T)$ — אין צורך בחילוק ממשי. סך הכול $O(|x|^2)$ , ואורך הפלט $O(|x|)$ .

מה זה קונה

$\mathrm{BIN\text{-}PACKING}$ היא NP-קשה — ובונוס מאותה הוכחה: הפלט תמיד משתמש ב- $k=2$ , ולכן הבעיה נשארת NP-קשה גם כשמספר התאים הוא קבוע. זו גם נקודת הפתיחה לחסם אי-הקירוב: אלגוריתם קירוב ביחס מוחלט טוב מ- $3/2$ היה מבחין בין $\mathrm{OPT}=2$ ל- $\mathrm{OPT}=3$ ולכן היה מכריע את $\mathrm{PARTITION}$ .

מלכודות

התנאי בשלב 2 חייב להיות $>$ ולא $\ge$ . אם $a_i=T/2$ בדיוק, אז $\{i\}$ מול המשלים היא חלוקה חוקית והקלט כן ב- $\mathrm{PARTITION}$ — ואילו הפלט של שלב 2 אינו ב- $\mathrm{BIN\text{-}PACKING}$ , והרדוקציה הייתה נשברת. עם $>$ הכול תקין, ואף מתקיים $b_i=1$ במקרה הגבול, שהוא ערך חוקי.
למה מ- $\mathrm{PARTITION}$ ולא מ- $\mathrm{SUBSET\text{-}SUM}$ . שוב עיקרון הבעיה הקרובה: ב- $\mathrm{PARTITION}$ אין סכום יעד חיצוני, וגם ב- $\mathrm{BIN\text{-}PACKING}$ אין — הקיבולת מוכתבת מבפנים. יציאה מ- $\mathrm{SUBSET\text{-}SUM}$ הייתה מחייבת להטמיע את $S$ שוב, עבודה שכבר נעשתה.

השרשרת

נשענת על

SUBSET-SUM ≤p PARTITION

משמשת בהמשך ל

PARTITION ≤p BIN-PACKING-OPT

מאיפה זה נקרא

שיעור 12משפט 4: $\mathrm{PARTITION} \le_p \mathrm{BIN\text{-}PACKING}$
תרגיל מודרךbin-packing-approximation
2026"בשאלה זו נוכיח כי בעיית $Bin\text{-}Packing$ שראינו בשיעור היא $NP$ -שלמה."