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

จาก Theory Wiki
ไปยังการนำทาง ไปยังการค้นหา
(หน้าที่ถูกสร้างด้วย 'ในเอกสาร 01204512/congestion1 เราวิเคราะห์กรณีกราฟพิเศษ ใน...')
 
(ย้อนการแก้ไขของ CarolAnderson (Talk) ไปยังรุ่นของ Jittat)
 
(ไม่แสดง 29 รุ่นระหว่างกลางโดยผู้ใช้ 2 คน)
แถว 1: แถว 1:
ในเอกสาร [[01204512/congestion1]] เราวิเคราะห์กรณีกราฟพิเศษ
+
: ''เอกสารนี้สำหรับรายวิชา [[01204512]] อ้างอิงจาก [http://www.cs.berkeley.edu/~satishr/cs270/sp12/ http://www.cs.berkeley.edu/~satishr/cs270/sp12/] lecture 1''
  
ในส่วนนี้เราจะวิเคราะห์กรณีทั่วไป จะวิเคราะห์ผ่านทางปัญหาทวิภาค (dual problem)  สำหรับการหาปัญหาทวิภาคนี้ เราจะพิจารณาละเอียดต่อไป
+
ในเอกสาร [[01204512/congestion1]] เราวิเคราะห์กรณีกราฟพิเศษ ที่มี paths ความยาว <math>1,2,\ldots,k</math> เชื่อมระหว่างจุดปลาย
  
สำหรับปัญหา congestion minimization
+
ในส่วนนี้เราจะวิเคราะห์กรณีทั่วไป โดยเราจะหา 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>
 +
 
 +
นั่นคือ 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 ไม่มีวันไปสู่จุดสมดุลย์ได้  เราจะพิจารณากรณีนี้ต่อไป

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

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

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

ในส่วนนี้เราจะวิเคราะห์กรณีทั่วไป โดยเราจะหา path ไปเรื่อย ๆ โดยใช้เส้นทางที่สั้นที่สุด ตามระยะทางบนเส้นเชื่อม ที่กำหนดให้เท่ากับ โดยที่ จะเป็นค่า congestion ในขณะนั้น

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

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

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

  • max
  • subject to:

หมายเหตุ เราเขียน แทนเซต

Lowerbound

สังเกตว่าสำหรับคำตอบใด ๆ ของปัญหา congestion minimization เป้าหมาย (max congestion) ที่ได้นั้น จะเป็น upper bound ของของเป้าหมายของคำตอบใด ๆ ของปัญหา dual นี้ กล่าวคือ พิจารณาคำตอบของปัญหา congestion minimization ที่ใช้ paths ระหว่างคู่ เราต้องการแสดงว่า

พิจารณา (เพราะว่า?)

สังเกตว่า (ในขั้นตอนที่ 2 เราสลับอันดับของการหาผลรวม)

นั่นคือ เราจะได้ว่า ตามต้องการ

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

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

เราจะใช้ weight ที่ได้จากระยะทาง นั่นคือ เราจะให้

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

สังเกตว่า เนื่องจากระยะทางของเส้นเชื่อม เท่ากับ พิจารณาทุก ๆ เส้นเชื่อม ที่ เราจะได้ว่า

ให้เซต แทนเซตของเส้นเชื่อม ที่มี เราจะได้ว่า

เนื่องจากผลรวมของระยะทางบน edge ทั้งหมดมีค่าไม่น้อยกว่า เราจะได้ว่า

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

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

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

นั่นคือ

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

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