ดูต้นฉบับสำหรับ 01204512/congestion2

: ''เอกสารนี้สำหรับรายวิชา [[01204512]] อ้างอิงจาก [http://www.cs.berkeley.edu/~satishr/cs270/sp12/ http://www.cs.berkeley.edu/~satishr/cs270/sp12/] lecture 1''

ในเอกสาร [[01204512/congestion1]] เราวิเคราะห์กรณีกราฟพิเศษ ที่มี paths ความยาว <math>1,2,\ldots,k</math> เชื่อมระหว่างจุดปลาย

ในส่วนนี้เราจะวิเคราะห์กรณีทั่วไป โดยเราจะหา path ไปเรื่อย ๆ โดยใช้เส้นทางที่สั้นที่สุด ตามระยะทางบนเส้นเชื่อม ที่กำหนดให้เท่ากับ <math>\ell(e)=2^{c(e)}</math> โดยที่ <math>c(e)</math> จะเป็นค่า congestion ในขณะนั้น

จะวิเคราะห์ผ่านทางปัญหาทวิภาค (dual problem)  สำหรับการหาปัญหาทวิภาคนี้ เราจะพิจารณาละเอียดต่อไปในภาคการศึกษานี้

สำหรับปัญหา congestion minimization ในปัญหาทวิภาคของปัญหาดังกล่าว เราต้องการหาค่า weight <math>w_e</math> ให้กับทุก ๆ edge <math>e</math> โดยที่ผลรวมของ weight มีค่าเท่ากับ 1 นอกจากนี้ ให้ <math>p_i</math> เป็น shortest path ระหว่าง <math>s_i</math> และ <math>t_i</math> ภายใต้ weight <math>w_e</math> เป้าหมายของเราคือพยายามจะ maximize ผลรวมของระยะทางสั้นที่สุดของทุก ๆ คู่ <math>(s_i,t_i)</math>  

ปัญหาดังกล่าวนิยามได้ดังนี้

* max <math>\sum_{i\in[k]} w(p_i)</math>
* subject to: <math>w_e\geq 0, \sum_{e\in E}w_e = 1</math>

หมายเหตุ เราเขียน <math>[k]</math> แทนเซต <math>\{1,2,3,\ldots,k\}</math>

== Lowerbound ==

สังเกตว่าสำหรับคำตอบใด ๆ ของปัญหา congestion minimization เป้าหมาย (max congestion) ที่ได้นั้น จะเป็น upper bound ของของเป้าหมายของคำตอบใด ๆ ของปัญหา dual นี้  กล่าวคือ พิจารณาคำตอบของปัญหา congestion minimization ที่ใช้ paths <math>p_i</math> ระหว่างคู่ <math>(s_i,t_i)</math>  เราต้องการแสดงว่า <math>\max_e c(e) \geq \sum_i w(s_i,t_i)</math>

พิจารณา <math>\max_e c(e) \geq \sum_e w(e)c(e)</math> (เพราะว่า?)

สังเกตว่า
<math>
\sum_i w(p_i)
=\sum_i\sum_{e\in p_i} w(e)
=\sum_e\sum_{p_i\ni e} w(e)
=\sum_e w(e)c(e)
</math>
(ในขั้นตอนที่ 2 เราสลับอันดับของการหาผลรวม)

นั่นคือ เราจะได้ว่า
<math>\max_e c(e) 
\geq \sum_e w(e)c(e)
= \sum_i w(p_i)
\geq \sum_i w(s_i,t_i)
</math>
ตามต้องการ

การพิสูจน์ในส่วนนี้ ทำให้เราสามารถใช้ weight ของปัญหา dual มาเพื่อ bound congestion ที่เกิดขึ้นกับ congestion ที่ดีที่สุดได้

== Congestion ที่ดีที่สุดกับ congestion ที่ได้เมื่อสมดุลย์ ==
เราจะใช้ weight ที่ได้จากระยะทาง <math>\ell(e)</math>  นั่นคือ เราจะให้

<center>
<math>w(e)=\frac{\ell(e)}{\sum_e \ell(e)}</math>
</center>

ให้ <math>c_{max}</math> แทนค่า congestion ที่ได้จากอัลกอริทีมที่ปรับค่าโดยใช้ฟังก์ชันยกกำลัง  ให้ <math>e^*</math> แทนเส้นเชื่อมที่มีค่า congestion เท่ากับ <math>c_{max}</math>

สังเกตว่า เนื่องจากระยะทางของเส้นเชื่อม <math>e</math> เท่ากับ <math>\ell(e)=2^{c(e)}</math>  พิจารณาทุก ๆ เส้นเชื่อม <math>e</math> ที่ <math>c(e)<c_{max}-2\log m</math>  เราจะได้ว่า

<center>
<math>\ell(e)=2^{c(e)}=2^{c_{max}-2\log m}=2^{c(e^*)-2\log m}=\frac{2^{c(e^*)}}{2^{2\log m}}=\frac{2^{c(e^*)}}{m^2}=\frac{\ell(e^*)}{m^2}</math>
</center>

ให้เซต <math>F</math> แทนเซตของเส้นเชื่อม <math>e</math> ที่มี <math>c(e)<c_{max}-2\log m</math>  เราจะได้ว่า

<center>
<math>\sum_{e\in F}\ell(e) = \sum_{e\in F}\frac{\ell(e^*)}{m^2}\leq m\frac{\ell(e^*)}{m^2}=\ell(e^*)/m</math>
</center>

เนื่องจากผลรวมของระยะทางบน edge ทั้งหมดมีค่าไม่น้อยกว่า <math>\ell(e^*)</math> เราจะได้ว่า 

<center>
<math>\sum_{e\in F}\ell(e)\leq\frac{1}{m}\sum_{e\in E}\ell(e)</math>
</center>

จากที่เราได้วิเคราะห์ในเรื่องของ lowerbound ข้างต้น เราจะได้ว่า

<math>
\begin{array}{rcl}
c_{opt} &\geq & \sum_i w(s_i,t_i)\\
&=& \sum_e w(e)c(e)\\
&=& \sum_e\frac{2^{c(e)}}{\sum_f 2^{c(f)}}\cdot c(e)
= \frac{\sum_{e\in E} 2^{c(e)}\cdot c(e)}{\sum_{e\in E} 2^{c(e)}}
\end{array}
</math>

ให้ <math>F'=E-F</math> (หรือจะแบ่ง <math>E</math> ออกเป็น <math>F</math> และ <math>F'</math>) เราจะได้ว่า

<math>
\begin{array}{rcl}
c_{opt} 
&=& \frac{\sum_{e\in E} 2^{c(e)}\cdot c(e)}{\sum_{e\in E} 2^{c(e)}}\\
&=& \frac{\sum_{e\in F} 2^{c(e)}\cdot c(e) + \sum_{e\in F'} 2^{c(e)}\cdot c(e)}
{\sum_{e\in F} 2^{c(e)} + \sum_{e\in F'} 2^{c(e)}}\\
&\geq& \frac{\sum_{e\in F} 2^{c(e)}\cdot c(e) + \sum_{e\in F'} 2^{c(e)}\cdot c(e)}
{(1+1/m)\sum_{e\in F'} 2^{c(e)}}\\
&\geq& \frac{\sum_{e\in F'} 2^{c(e)}\cdot c(e)}
{(1+1/m)\sum_{e\in F'} 2^{c(e)}}
\geq \frac{(c_{max}-2\log m)\sum_{e\in F'} 2^{c(e)}}
{(1+1/m)\sum_{e\in F'} 2^{c(e)}}\\
&=& \frac{(c_{max}-2\log m)}{(1+1/m)}\frac{\sum_{e\in F'} 2^{c(e)}}{\sum_{e\in F'} 2^{c(e)}}
=\frac{c_{max}-2\log m}{1+1/m}
\end{array}
</math>

นั่นคือ <math>c_{max} \leq (1+1/m)c_{opt} + 2\log m</math>

== เรื่องราวที่ซ่อนไว้ ==