204512/บรรยาย 12

---

จดบันทึกคำบรรยายโดย:

นาย ชาคริต กิตโร รหัส 50653757

นาย รักพงค์ แก้วพวง รหัส 50653880

---

Min-cost flow

ให้กราฟ $G=(V,E)$ ความจุ $c(x,y)$ บนเส้นเชื่อม $(x,y)$ หา Max-flow ที่ cost ต่ำที่สุด for flow $f$

$cost(f)=\sum _{c\in E}^{}{c(e)}\cdot f(e)$

ให้ Max flow $f$ หาว่า $f$ เป็น min-cost หรือไม่ ให้ $G_{f}$ เป็น residual graph ของ $f$

Thm Max flow $f$ เป็น min-cost เมื่อ และต่อเมื่อไม่มี negative cost cycle $w$

Prof พิสูจน์ว่า $f$ เป็น min-cost จะไม่มี negative cost cycle ใน $G_{f}$

Assume $f$ เป็น min-cost และมี negative cost cycle ใน $G_{f}$

?รูป

augment ไปตาม cycle $w$ ทำให้ cost ของ flow ต่ำลง → $f$ ไม่ใช่ min-cost flow contradiction

Prof พิสูจน์ว่า ถ้า $f$ ไม่มี min-cost flow จะมี negative cost cycle ใน $Gf$

ให้ $f^{*}$ เป็น min-cost max flow

พิจารณา $f^{*}$$-f$ มองในเชิงของ flow; $cost(f^{*})<cost(f)$

พิจารณา $f^{*}$$-f$ → เป็น cyculation ลบกันแล้วหักล้างกัน

$cost(f^{*}-f)$$=diff(cost(f^{*}),cost(f))$

ทำให้ $cost(f^{*}-f)=cost$ เป็นลบ แสดงว่าต้องมี cycle อย่างน้อย 1 อัน เป็นลบ

$cost(f^{*}-f)=$$cost(f^{*})-$$cost(f)$$<0$ <- $c=f^{*}-$$f$

$cost(c)=$ผลรวมของ circulation ที่แต่ละวงเป็น cycle ที่มี cost รวมเป็นลบ

ดังนั้นมีบาง cycle ที่มี cost เป็นลบ

Negative cost cycle cancelling algorithm

1. หา max flow $f$

 Repeat
   หา negative cost cycle ใน $G_{f}$
   cancel $w$ จาก $f$
 Until ไม่มี negative cost cycle ใน $G_{f}$

Running Time

ถ้า cost เป็น integer และ cap เป็น integer

นิยาม $c=$max cost, $u=$max cap, $n=|u|,m=|E|$

ในแต่ละรอบ cost ของ flow จะลดลงอย่างน้อย 1 หน่วย

bound ของ cost เป็น $cost<=m.u.c$

แต่ละรอบใช้เวลาหา negative cost cycle ใช้ belman-ford ใช้เวลา $O(m.n)$

รวม $O(n.m^{2}.u.c)$

cancel cycle $w$ ที่ทำให้ cost ลดลงมากที่สุด

cancel cycle ที่มี minimum mean cost → ได้ algorithm ที่ run ใน strongly polynomial time

weakly polynomial time = poly(n m log u log c)

strongly polynomial time = poly(n m)

Shortest Paths

ระยะทาง D: V-> R เงื่อนไขที่ D เป็น shortest path

$\forall e=(x,y):D(y)<=D(x)+l(x,y)$

D(x)+l(x,y)-D(y)>=0

Price Function reduced cost

เรียก function p : V-> R ว่าเป็น price function สำหรับ price function p นิยาม reduced cost Cp(x,y) = p(x) + c(x,y)-p(y)

พิจารณา path P = $V_{0},V_{1},....,V_{k}$ ความยาวของ P บน Cp คือ $Cp(P)=\sum \limits _{i=1}^{k}{Cp(V{i-1},V)}=P(V{0})+C(V{0},V{1})-P(V{1})+P(V{1})+C(V{1},V{2})-P(V{2})+P(V{2})+C(V{2},V{3})-P(V{3})...+P(V{k-1})+C(V{k-1},V{k})-P(V{k})$

$=P(V{0})+\sum \limits _{i=1}^{k}{(V{i-1},V{1})}-P(V{k})$ $=P(V{0})+C(P)-P(V{k})$

พิจารณา cycle W Cp(W)=C(W) หมายเหตุ : ยังไม่ได้ใส่รูป การใช้ reduced cost ไม่มีผลต่อการมีอยู่ของ negative cost cycle

จะกล่าวว่า Price function P เป็น feasible price function ถ้า $\forall edge(x,y)=cp((x,y)>=0$

Lemma : ถ้ากราฟมี negative cost cycle จะไม่มี feasible price function

Proof.

หมายเหตุ : ยังไม่ได้ใส่รูป

พิจารณา price function p ใดๆ พิจารณา negative cost cycle W Cp(W)=C(W)<0 นั่นคือมีบาง edge

${e\in W}$

ที่ Cp(e) < 0 นั่นคือ p ไม่ feasible

Optimulity condition

1. ไม่มี negative cost cycle ใน $G_{f}$
2. Thm flow $f$ จะเป็น min cost flow ถ้ามี price function $P$

Assume กราฟไม่มี negative cost cycle หา shortest path จาก $s$ ใดๆ แล้วให้ $D(u)=$ระยะทางสั้นที่สุดจาก $s$→$t$

Observation 1 $D$ เป็น feasible price function → $D(x)+C(x,y)-D(y)=0$

Observation 2 ถ้าพิจารณา shortest path $p$ จาก $s$ ไปยัง node ใดๆ ทุกๆ edge $e$ บน $p$ มี ::$C$_D$(v,e)=0$

$D(v)=D(u)+C(u,v)$

$C$_D$(u,v)=D(u)+C(u,v)-D(v)$

Successive Shortest Path

เป็น Algorithm ที่ใช้่ในการหา Max flow จาก s ไป t    

      f<- Zero Flow
      Repeat :
           หา min cost path บน Gf (*) จาก s ไป t 
       (ด้วย shortest path algorithm ที่ทำงานบนกราฟที่มี cost เป็นลบได้ เช่น Belman-Ford)
           augment flow ตาม path นั้น
      until f เป็น max flow

Running Time
1. หา shortest path O(mn) ต่อรอบ
2. augment flow ทั้งหมด <= mC รอบ
3. ทำงานในเวลา O(n$m^{2}$C)

Lemma2: ในแต่ละรอบที่ augment flow f ที่ได้เป็น min cost flow

proof : ในรอบแรก f เป็น zero flow เป็น min cost

   พิจารณาการ augment ในรอบที่ i
       - flow f ก่อนการ augment เป็น min cost flow 
         ใน Gf ไม่มี negative cost cycle
       - ให้ d(u) เป็นระยะทางสั้นที่สุดยน Gf จาก s ที่หาได้ในขึ้นตอน(*)
         จาก observation 2 จะได้ว่า Cd(e)=0 สำหรับทุกๆ edge e บน  shortest path จาก s ไป t

             *ยังไม่ได้ใส่รูป

  ให้ $f^{'}$ เป็น flow ที่ได้จากหลักการ augment 
  พิจารณา G$f^{'}$ 
       claim : d เป็น feasible price function บน G$f^{'}$ 
  พิจารณา  edge(x,y) บน G$f^{'}$ 
       case1: ${(x,y)\in Gf}$
       case2: ${(x,y)\notin Gf}$ นั่นคือ ${(y,x)\in Gf)}$ C(y,x) shortest path และถูก augment
    
       นั่นคือ Cd(y,x)=0 
            Cd(x,y)=d(x)+c(x,y)-dy
            = -(-d(x)-c(x,y)+dy)
            = -(dx(x)+c(x,y)-dy)
            = -Cd(y,x) 
             -Cd(y,x)>=0
นั้นคือ ${f^{'}}$ เป็น min cost flow

Ford Fulkerson + Capacity Scalling

 มี parameter Δ เป็น scale บอกว่าจะ augment flow ใน path ครั้งละ Δ หน่วย
 ให้ Δ $=m.u$, $f=$Zero flow
 Repeat
   Repeat
     หา $Gf$, หา augmenting path ที่มี cap $>=$ Δ
     เติม augment Δ หน่วย
   until หา augmenting path ขนาด Δ ไม่ได้
 Δ $=$ Δ $/2$
 until Δ $<1$

Capacity scalling min cost flow

แต่ละ node จะมี demand $b(u)$

โดย parameter Δ จะเติม flow ครั้งละ Δ

ให้

$s($Δ$)$ เป็นเซตของ node $u$ ที่ $b(u)>=$ Δ

$t($Δ$)$ เป็นเซตของ node $u$ ที่ $b(u)<=$ &minus Δ

$G_{f}($Δ$)$ เป็น residual graph ที่ทุก edge มี cap อย่างน้อย Δ

รูป?

หลังจาก Δ augment flow ที่เหลือไม่เกิน Δ

$G_{f}($Δ$)$ ไม่มี negative cost cycle → มี feasible price function

Δ$/2=G_{f}($Δ$/2)$

อาจมี negative cost cycle นั้นคือ $f$ ไม่มี min cost บน $edge(x,y)$ ที่ $C_{d}<0$

$saturate(x,y)$ สร้างคู่ demand excess