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