ผลต่างระหว่างรุ่นของ "01204512/congestion2"

รุ่นแก้ไขปัจจุบันเมื่อ 06:03, 5 สิงหาคม 2555

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

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

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

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

สำหรับปัญหา congestion minimization ในปัญหาทวิภาคของปัญหาดังกล่าว เราต้องการหาค่า weight $w_{e}$ ให้กับทุก ๆ edge $e$ โดยที่ผลรวมของ weight มีค่าเท่ากับ 1 นอกจากนี้ ให้ $p_{i}$ เป็น shortest path ระหว่าง $s_{i}$ และ $t_{i}$ ภายใต้ weight $w_{e}$ เป้าหมายของเราคือพยายามจะ maximize ผลรวมของระยะทางสั้นที่สุดของทุก ๆ คู่ $(s_{i},t_{i})$

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

max $\sum _{i\in [k]}w(p_{i})$
subject to: $w_{e}\geq 0,\sum _{e\in E}w_{e}=1$

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

Lowerbound

สังเกตว่าสำหรับคำตอบใด ๆ ของปัญหา congestion minimization เป้าหมาย (max congestion) ที่ได้นั้น จะเป็น upper bound ของของเป้าหมายของคำตอบใด ๆ ของปัญหา dual นี้ กล่าวคือ พิจารณาคำตอบของปัญหา congestion minimization ที่ใช้ paths $p_{i}$ ระหว่างคู่ $(s_{i},t_{i})$ เราต้องการแสดงว่า $\max _{e}c(e)\geq \sum _{i}w(s_{i},t_{i})$

พิจารณา $\max _{e}c(e)\geq \sum _{e}w(e)c(e)$ (เพราะว่า?)

สังเกตว่า $\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)$ (ในขั้นตอนที่ 2 เราสลับอันดับของการหาผลรวม)

นั่นคือ เราจะได้ว่า $\max _{e}c(e)\geq \sum _{e}w(e)c(e)=\sum _{i}w(p_{i})\geq \sum _{i}w(s_{i},t_{i})$ ตามต้องการ

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

Congestion ที่ดีที่สุดกับ congestion ที่ได้เมื่อสมดุลย์

เราจะใช้ weight ที่ได้จากระยะทาง $\ell (e)$ นั่นคือ เราจะให้

$w(e)={\frac {\ell (e)}{\sum _{e}\ell (e)}}$

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

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

$\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}}}$

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

$\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$

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

$\sum _{e\in F}\ell (e)\leq {\frac {1}{m}}\sum _{e\in E}\ell (e)$

นั่นคือ edge เซต $F$ มีน้ำหนักต่ำมากกว่าเซตของ edge ที่เหลือ

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

${\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}}$

ให้ $H=E-F$ (หรือจะแบ่ง $E$ ออกเป็น $F$ และ $H$ โดยที่เซต $H$ จะเป็นเซตที่ weight ส่วนมากอยู่) เราจะได้ว่า

${\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 H}2^{c(e)}\cdot c(e)}{\sum _{e\in F}2^{c(e)}+\sum _{e\in H}2^{c(e)}}}\\&\geq &{\frac {\sum _{e\in F}2^{c(e)}\cdot c(e)+\sum _{e\in H}2^{c(e)}\cdot c(e)}{(1+1/m)\sum _{e\in H}2^{c(e)}}}\\&\geq &{\frac {\sum _{e\in H}2^{c(e)}\cdot c(e)}{(1+1/m)\sum _{e\in H}2^{c(e)}}}\geq {\frac {(c_{max}-2\log m)\sum _{e\in H}2^{c(e)}}{(1+1/m)\sum _{e\in H}2^{c(e)}}}\\&=&{\frac {(c_{max}-2\log m)}{(1+1/m)}}\cdot {\frac {\sum _{e\in H}2^{c(e)}}{\sum _{e\in H}2^{c(e)}}}\\&=&{\frac {c_{max}-2\log m}{1+1/m}}\end{array}}$

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

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

ในการวิเคราะห์ที่เราทำมา เราสมมติว่าเราสามารถไปสู่จุดสมดุลย์ได้ ในความเป็นจริง เป็นไปได้ที่เมื่อเพิ่ม path ใหม่มา ก็จะทำให้ระยะทางบน edge ไม่มีวันไปสู่จุดสมดุลย์ได้ เราจะพิจารณากรณีนี้ต่อไป

@@ แถว 1: / แถว 1: @@
-: ''เอกสารนี้สำหรับรายวิชา [[01204512]] อ้างอิงจาก [http://www.cs.berkeley.edu/~satishr/cs270/sp12/ http://www.cs.berkeley.edu/~satishr/cs270/sp12/] lecture 1
+: ''เอกสารนี้สำหรับรายวิชา [[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> เชื่อมระหว่างจุดปลาย
-ในส่วนนี้เราจะวิเคราะห์กรณีทั่วไป จะวิเคราะห์ผ่านทางปัญหาทวิภาค (dual problem)  สำหรับการหาปัญหาทวิภาคนี้ เราจะพิจารณาละเอียดต่อไป
+ในส่วนนี้เราจะวิเคราะห์กรณีทั่วไป โดยเราจะหา 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>
@@ แถว 13: / แถว 15: @@
 หมายเหตุ เราเขียน <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>
+นั่นคือ edge เซต <math>F</math> มีน้ำหนักต่ำมากกว่าเซตของ edge ที่เหลือ
+จากที่เราได้วิเคราะห์ในเรื่องของ 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>H=E-F</math> (หรือจะแบ่ง <math>E</math> ออกเป็น <math>F</math> และ <math>H</math> โดยที่เซต <math>H</math> จะเป็นเซตที่ weight ส่วนมากอยู่) เราจะได้ว่า
+<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 H} 2^{c(e)}\cdot c(e)}
+{\sum_{e\in F} 2^{c(e)} + \sum_{e\in H} 2^{c(e)}}\\
+&\geq& \frac{\sum_{e\in F} 2^{c(e)}\cdot c(e) + \sum_{e\in H} 2^{c(e)}\cdot c(e)}
+{(1+1/m)\sum_{e\in H} 2^{c(e)}}\\
+&\geq& \frac{\sum_{e\in H} 2^{c(e)}\cdot c(e)}
+{(1+1/m)\sum_{e\in H} 2^{c(e)}}
+\geq \frac{(c_{max}-2\log m)\sum_{e\in H} 2^{c(e)}}
+{(1+1/m)\sum_{e\in H} 2^{c(e)}}\\
+&=& \frac{(c_{max}-2\log m)}{(1+1/m)}\cdot\frac{\sum_{e\in H} 2^{c(e)}}{\sum_{e\in H} 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>
+== เรื่องราวที่ซ่อนไว้ ==
+ในการวิเคราะห์ที่เราทำมา เรา'''สมมติ'''ว่าเราสามารถไปสู่จุดสมดุลย์ได้ ในความเป็นจริง เป็นไปได้ที่เมื่อเพิ่ม path ใหม่มา ก็จะทำให้ระยะทางบน edge ไม่มีวันไปสู่จุดสมดุลย์ได้  เราจะพิจารณากรณีนี้ต่อไป

ผลต่างระหว่างรุ่นของ "01204512/congestion2"

รุ่นแก้ไขปัจจุบันเมื่อ 06:03, 5 สิงหาคม 2555

Lowerbound

Congestion ที่ดีที่สุดกับ congestion ที่ได้เมื่อสมดุลย์

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

รายการเลือกการนำทาง

เครื่องมือส่วนตัว

เนมสเปซ

สิ่งที่แตกต่าง

ดู

เพิ่มเติม

ค้นหา

การนำทาง

เครื่องมือ