הוכחה שהבעיה היא NPC

[sivz]

הוכחה שהבעיה היא NPC

השאלה היא כזו: להוכיח שהבעיה הנ"ל היא NP שלמה ברדקציה פשוטה. למנהל משרד M עובדים וN משימות. אותן הוא רוצה לחלק בין העובדים. המשימות מתקבלות כסדרה (t1,....tn ) כאשר ti הוא הזמן שלוקח לבצע את המשימה הi. לא ניתן לחלק משימה בודדת בין שני עובדים. על עובד שמתחיל משימה, לבצע אותה ברצף עד סיומה, רק לאחר מכן הוא יכול לבצע את המשימה הבאה שניתנה לו. מתחילים לספור זמן מהרגע שכל העובדים מתחילים לעבוד ועוצרים את הסטופר ברגע שכל המשימות בוצעו. המטרה: לחלק את המשימות בין העובדים כך שכל המשימות ייתבצעו תוך זמן מינימילי. חשבתי שאולי ניתן לעשות את הרדוקציה מ set cover או vertex cover אבל אני לא בטוחה. אולי למישהו יש רעיון לבניה?

 

[dorba]

רדוקציה מ-PARTITION

תזכורת : בעיית הPARTITION מוגדרת כך: בהינתן קבוצה של מספרים A1,A2,A3,A4....AK האם ניתן לחלק אותם לשתי קבוצות כך שסכום הערכים בכל קבוצה יהיה שווה ( סכום הערכים לא מספר האיברים!). זו בעיית NP קשה. הרדוקציה כעת פשוטה. בהינתן בעיית PARTITION המירי בזמן פולינימיאלי לINSTANCE של הבעייה שלך : A1,A2,A3,A4....AK ילכו ל(t1,....tK ) דהיינו ל-K משימות. M=2. והזמן המינימלי (כבעיית אופטימיזציה) יהיה חצי הסכום של t1,....tK .