Question

spring_15_b
max_flow
binary_search

בשער הטכניון עובדים nn מאבטחים g1,,gng_1, \ldots, g_n. עליכם לקבוע עבורם את לוח המשמרות. ישנן mm משמרות, וכל מאבטח הגיש לכם רשימה עם משמרות אותן הוא יכול לבצע.

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

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

על האלגוריתם לרוץ בזמן O(m2n)O(m^2n).

ב. לאחר שיושם לוח המשמרות שקבע האלגוריתם מסעיף א', התלוננו חלק מהמאבטחים על חוסר שוויון בחלוקת המשמרות.

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

1

Answers

א. נראה רדוקציה לבעיית זרימה:

N=(G,c,s,t)N = (G, c, s, t)

כאשר

G=({s}{g1,,gn}{s1,,sm}{t},E)G = (\{s\} \cup \{g_1, \ldots, g_n\} \cup \{s_1, \ldots, s_m\} \cup \{t\}, E)

E={sgi}1in{gisj:guard i can be assigned to shift j }{sjt}1jmE = \{sg_i\}_{1 \leq i \leq n} \cup \{g_is_j : \text{guard i can be assigned to shift j }\} \cup \{s_jt\}_{1 \leq j \leq m}

c(sgi)=k,c(gisj)=1,c(sjt)=2c(sg_i) = k, c(g_is_j) = 1, c(s_jt) = 2

כלומר, הרשת נראית כך:

נשים לב שכל הקיבולים שלמים ולכן קיימת זרימת מקסימום בשלמים. כמו כן, נשים לב שקיבול החתך שמכיל את כל הצמתים פרט ל-tt הוא 2m2m ולכן זרימת המקסימום חסומה על ידי 2m2m.

טענה: קיים שיבוץ חוקי של מאבטחים אמ"מ קיימת זרימה עם ערך 2m2m ברשת הזרימה המתאימה.

הוכחה: בהינתן זרימה, ff, עם ערך 2m2m נשבץ את השומר ה-ii למשמרת ה-jj אמ"מ f(gisj)=1f(g_is_j) = 1 (צריך להראות ששיבוץ כזה מקיים את האילוצים).

מצד שני, בהינתן שיבוץ חוקי, נגדיר זרימה:

f(sgi)=# of shifts guard i assigned tof(gisj)={1guard i assigned to shift j0otherwisef(sjt)=2 f(sg_i) = \text{\# of shifts guard i assigned to} \\ f(g_is_j) = \begin{cases} 1 & \text{guard i assigned to shift j} \\ 0 & \text{otherwise} \\ f(s_jt) = 2 \end{cases}

(צריך להראות שזו אכן זרימה)

אלגוריתם:

  • צור את רשת הזרימה המתאימה וחשב זרימת מקסימום שלמה
  • אם ערך הזרימה קטן מ-2m2m החזר כי לא קיים שיבוץ מתאים
  • אחרת החזר את השיבוץ המתאים כמתואר בטענה

נכונות: מיידי מהטענה.

סיבוכיות: נשים לב שגודל הגרף הוא O(nm)O(nm) וערך זרימת המקסימום היא O(m)O(m) ולכן ניתן לחשב זרימת מקסימום בזמן O(m2n)O(m^2n). את התרגום לשיבוץ אפשר לעשות בזמן לינארי.

ב. נשים לב שמספר המשמרות המקסימלי שמאבטח מסוגל לעשות הוא mm ולכן ניתן לבצע חיפוש בינרי על הטווח 1,,m1,\ldots,m ובכל פעם להפעיל את האלגוריתם מסעיף א.

נכונות: נובע מנכונות האלגוריתם של סעיף א.

סיבוכיות: O(m2nlogm)O(m^2n \log m ).

1
Feedback