Question

max_flow
greedy
spring17_a

נתון מספר טבעי nN{0}n \in \mathbb{N} \setminus \{0\}.

ברצוננו לחשב מטריצה MRn×nM \in \mathbb{R}^{n \times n}, על ידי קביעת ערך לכל אחד מ-n2n^2 הנעלמים שבמטריצה (נסמן את הנעלם שבשורה ה-ii ובעמודה ה-jj ב-mijm_{ij}).

לכל שורה i[n]i \in [n] נתון אילוץ: j=1nmijri\sum_{j = 1}^n m_{ij} \leq r_i, ולכל עמודה j[n]j \in [n] נתון אילוץ i=1nmijcj\sum_{i = 1}^n m_{ij} \leq c_j.

בנוסף, לכל i,j[n]i,j \in [n] נתון אילוץ 0mijbij0 \leq m_{ij} \leq b_{ij}.

כל הקבועים הם ממשיים ואי-שליליים, משמע: i,j[n]:ri,cj,bijR0\forall i,j \in [n]: r_i, c_j, b_{ij} \in \mathbb{R}_{\geq 0}

נגדיר:

  • השמה חוקית: קביעת ערך לכל אחד מ-n2n^2 הנעלמים, כך שכל האילוצים מתקיימים.
  • ערך של השמה: סכום איברי המטריצה: i,j[n]mij\sum_{i,j \in [n]} m_{ij}.

1. הציעו אלגוריתם המחזיר השמה חוקית בעלת ערך גבוה ביותר. על האלגוריתם לרוץ בסיבוכיות זמן O(n5)O(n^5).

2. בסעיף זה נתון שלכל i,j[n]i,j \in [n] מתקיים bij=b_{ij} = \infty (כלומר אין חסם עליון על ערכי הנעלמים).

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

שימו לב: פתרונות טריוויאלים המריצים את סעיף 1. לא יתקבלו.

1

Answers

1. נראה רדוקציה לרשת זרימה:

N=(G=({s}{ri}i[n]{cj}j[n]{t},E),c)N = (G = (\{s\} \cup \{r_i\}_{i \in [n]} \cup \{c_j\}_{j \in [n]} \cup \{t\}, E), c)

כאשר

E={(s,ri)}i[n]{(ri,cj)}i,j[n]{(cj,t)}j[n]E = \{(s, r_i)\}_{i \in [n]} \cup \{(r_i, c_j)\}_{i,j \in [n]} \cup \{(c_j, t)\}_{j \in [n]}

ן-

c(s,ri)=ric(ri,cj)=bijc(cj,t)=cj \begin{array}{l} c(s, r_i) = r_i \\ c(r_i, c_j) = b_{ij} \\ c(c_j, t) = c_j \end{array}

נשים לב שמספר הצמתים בגרף הוא O(n)O(n)ומספר הקשתות O(n2)O(n^2) ולכן ניתן למצוא זרימת מקסימום בזמן O(n5)O(n^5). קל לוודא שיש התאמה חח"ע בין זרימה להשמה (ערך המשתנה mijm_{ij} שווה לערך הזרימה על הקשת (ri,cj)(r_i, c_j)), ומכאן נכונות האלגוריתם.

2. אם אין אילוצים על ערכי המשתנים אז ניתן לעבור על כל המשתנים פעם אחת ולעלות את ערכם כמה שאפשר מבלי להפר את אילוץ השורה והעמודה המתאימות. ניתן לעשות זאת בסיבוכיות O(n2)O(n^2).

1
Feedback