PARTITION ≤p BIN-PACKING-OPT

הבנייה

מאיפה מגיע המספר $3/2$ . הרדוקציה $\mathrm{PARTITION}\le_p\mathrm{BIN\text{-}PACKING}$ מייצרת מופע שסכום כל פריטיו הוא בדיוק $2$ וכל פריט בקטע $(0,1]$ . במופע כזה:

$\mathrm{OPT}\ge2$ תמיד, שכן קיבולת תא היא $1$ וסכום הפריטים $2$ , ולכן שני תאים הם המינימום האפשרי;
$\mathrm{OPT}=2$ אם ורק אם קיימת חלוקה שווה — כלומר אם ורק אם המופע המקורי ב- $\mathrm{PARTITION}$ ;
אחרת $\mathrm{OPT}\ge3$ .

כלומר האופטימום מקבל רק אחד משני ערכים, $2$ או $3$ , וההבחנה ביניהם שקולה להכרעת $\mathrm{PARTITION}$ . זהו "פער" קלאסי: ערכי הביניים ריקים.

האלגוריתם. נניח בשלילה שקיים אלגוריתם קירוב $A$ ביחס מוחלט $\rho<\tfrac32$ . נבנה מכריע ל- $\mathrm{PARTITION}$ :

על קלט $(a_1,\dots,a_n)$ , הרץ את הרדוקציה $\mathrm{PARTITION}\le_p\mathrm{BIN\text{-}PACKING}$ וקבל מופע $(b_1,\dots,b_n)$ שסכומו $2$ .
הרץ את $A$ עליו וקבל מספר תאים $\mathrm{ALG}$ .
אם $\mathrm{ALG}\le2$ — קבל; אחרת — דחה.

המחשה

bᵢ = 2aᵢ/S · Σbᵢ = 2 · bᵢ ∈ (0,1] · קיבולת 1

פריט מנורמל bᵢקיבולת תא 1

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

PARTITION ∈ ⟹ BIN-PACKING-OPT ∈

נניח $(a_1,\dots,a_n)\in\mathrm{PARTITION}$ . לפי נכונות הרדוקציה, המופע שנבנה ניתן לאריזה בשני תאים, כלומר $\mathrm{OPT}=2$ .

מכיוון ש- $A$ הוא אלגוריתם קירוב ביחס $\rho$ לבעיית מינימיזציה, $\mathrm{ALG}\;\le\;\rho\cdot\mathrm{OPT}\;=\;2\rho\;<\;2\cdot\tfrac32\;=\;3 .$ מספר התאים הוא מספר שלם, ו- $\mathrm{ALG}<3$ גורר $\mathrm{ALG}\le2$ . לכן שלב 3 מקבל.

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

BIN-PACKING-OPT ∈ ⟹ PARTITION ∈

נניח $(a_1,\dots,a_n)\notin\mathrm{PARTITION}$ . לפי נכונות הרדוקציה, המופע שנבנה אינו ניתן לאריזה בשני תאים, ומכיוון ש- $\mathrm{OPT}\ge2$ תמיד — נובע $\mathrm{OPT}\ge3$ .

אלגוריתם קירוב מחזיר פתרון אפשרי, כלומר אריזה חוקית, ואריזה חוקית אינה יכולה להשתמש בפחות תאים מהאופטימום. לכן $\mathrm{ALG}\;\ge\;\mathrm{OPT}\;\ge\;3\;>\;2 ,$ ולכן שלב 3 דוחה.

סיום. האלגוריתם מכריע את $\mathrm{PARTITION}$ בזמן פולינומי (הרדוקציה פולינומית, $A$ פולינומי מעצם ההגדרה, וההשוואה קבועה). אך $\mathrm{PARTITION}$ היא NP-קשה, ולכן $\mathrm{NP}\subseteq\mathrm{P}$ , כלומר $\mathrm{P}=\mathrm{NP}$ .

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

זמןO(|x|²) plus one call to A

מקוםO(|x|)

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

העלות היא בדיוק עלות הרדוקציה $\mathrm{PARTITION}\le_p\mathrm{BIN\text{-}PACKING}$ ( $O(|x|^2)$ ), בתוספת קריאה יחידה ל- $A$ והשוואה אחת.

מה זה קונה

אין אלגוריתם פולינומי לאריזה למכלים ביחס מוחלט טוב מ- $\tfrac32$ , אלא אם $\mathrm{P}=\mathrm{NP}$ . שימו לב שזה אינו סותר את קיומו של אלגוריתם First-Fit ביחס $2$ , ואף לא סכמות קירוב אסימפטוטיות — התוצאה חוסמת את היחס המוחלט בלבד, וההבחנה הזאת היא כל העניין.

מלכודות

היחס המוחלט מול היחס האסימפטוטי. התוצאה נשענת כולה על מופעים שבהם $\mathrm{OPT}\in\{2,3\}$ — מספרים קטנים. יחס אסימפטוטי מתעניין בהתנהגות כאשר $\mathrm{OPT}\to\infty$ , ושם החסם הזה אינו אומר דבר. ערבוב בין השניים הוא הטעות הנפוצה בשאלה הזאת.
השלמות של מספר התאים היא הצעד הקריטי. $\mathrm{ALG}<3$ גורר $\mathrm{ALG}\le2$ רק מפני שמספר התאים שלם. בבעיית מינימיזציה עם ערכים רציפים אותו טיעון לא היה עובד, וזו הסיבה שהחסם הזה שייך דווקא לאריזה למכלים.

השרשרת

נשענת על

PARTITION ≤p BIN-PACKING

מאיפה זה נקרא

שיעור 25תרגיל 7: קירוב $1.49$ ל- $\mathrm{BIN\text{-}PACKING}$ גורר $\mathrm{P}=\mathrm{NP}$
שיעור 12משפט 5 (בונוס של אותה הוכחה): $\mathrm{BIN\text{-}PACKING}$ נשארת NP-hard גם כאשר $k=2$ קבוע
תרגיל מודרךbin-packing-approximation