01204512/congestion2

เอกสารนี้สำหรับรายวิชา 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 ไม่มีวันไปสู่จุดสมดุลย์ได้ เราจะพิจารณากรณีนี้ต่อไป