01204512/congestion1

หน้านี้เป็นเอกสารประกอบวิชา 01204512 เนื้อหาจาก http://www.cs.berkeley.edu/~satishr/cs270/sp12/ lecture 1

เนื้อหายังไม่เรียบร้อย... น่าจะแก้เสร็จภายในวันนี้ (หลังเลิกเรียน)

ปัญหา congestion minimization

ให้กราฟ $G=(V,E)$ และเซตของคู่ของจุดยอด $(s_{1},t_{1}),(s_{2},t_{2}),\ldots ,(s_{k},t_{k})$ จำนวน $k$ คู่ เราต้องการหาเซตของเส้นทาง (path) ที่เชื่อมจุดยอดแต่ละคู่ โดยต้องการทำให้จำนวน path ที่ผ่านเส้นเชื่อมใด ๆ มีค่าน้อยที่สุด (เราจะเรียกจำนวนผ่านที่ผ่านเส้นเชื่อมใด ๆ ว่าเป็น congestion ของเส้นเชื่อมนั้น)

คำตอบใด ๆ ของปัญหานี้ คือเซตของ path จำนวน $k$ เส้น แต่เราต้องการให้ path เหล่านี้ กระจายกันไป path เหล่านี้ทำให้เกิด congestion บนเส้นเชื่อม เป้าหมายที่เราต้องการจะทำให้มีค่าต่ำสุดของปัญหานี้คือ congestion ที่มากที่สุดบนเส้นเชื่อมใด ๆ

ถ้าเขียนให้ชัดเจนก็คือ เราต้องการจะ:

หา path: $p_{1},p_{2},\ldots ,p_{k}$

ที่ $p_{i}$ เชื่อมระหว่าง $s_{i}$ กับ $t_{i}$ สำหรับ $1\leq i\leq k$

เพื่อจะ minimize $\max _{e\in E}c(e)$

เมื่อ $c(e)$ คือจำนวน path ที่ผ่านเส้นเชื่อม $e$

ปัญหานี้อาจจะยากสักหน่อย เราจะพิจารณาปัญหาที่ง่ายลง แทนที่เราจะ minimize ค่า congestion ที่สูงที่สุด เราจะ minimize ค่าเฉลี่ยของ congestion กล่าวคือ เราจะ:

minimize ${\frac {1}{m}}\sum _{e\in E}c(e)$, เมื่อ $m$ แทนจำนวนเส้นเชื่อม

สังเกตว่าผลรวมของ congestion บนทุก ๆ เส้นเชื่อมนั้น เท่ากับผลรวมของความยาวของทุก ๆ path ดังนั้นเป้าหมายที่เราต้องการจะ minimize คือ

${\frac {\sum _{i}\ell (p_{i})}{m}}$

ซึ่งปัญหานี้ เราสามารถแก้ได้โดยง่าย โดยใช้อัลกอริทึมสำหรับ shortest path

สังเกตเพิ่มเติมว่า ค่าคำตอบของปัญหา average congestion minimization นี้ เป็น lower bound ของค่าของคำตอบของปัญหา congestion minimization (เพราะอะไร?) ดังนั้น ถ้าเราจะแก้ปัญหา congestion minimization โดยการใช้วิธีของปัญหาแรกเลยจะได้หรือไม่?

ถ้าเราพิจารณาให้ดี เราจะพบว่า มีตัวอย่างง่าย ๆ ที่ผลลัพธ์ที่ได้ มี congestion เท่ากับ $k$ ในขณะที่คำตอบที่ดีที่สุดให้ congestion แค่ 1 เท่านั้น

สังเกตว่าทุก ๆ path จะพยายามไปใช้เส้นทางที่สั้นที่สุดพร้อม ๆ กันหมด เราจะพยายามแก้ปัญหานี้โดยการทำให้เส้นทางที่สั้นที่สุดมีความ "น่าใช้" ลดลงเรื่อย ๆ เราจะทดลองหลาย ๆ แบบ

การปรับระยะทางแบบเชิงเส้น

เราจะปรับความยาวของ edge ตาม congestion ของ edge นั้น กล่าวคือ ในแต่ละรอบที่เราหาเส้นทางที่สั้นที่สุดเราจะให้ $\ell (e)=c(e)$ สำหรับทุก ๆ เส้นเชื่อม เราจะทยอยเพิ่ม path เข้าไปในระบบจนกว่าระบบจะ "นิ่ง"

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

สังเกตว่าในกรณีนี้ ความยาวของ edge ใน path ที่มี edge เดียว (เส้นล่างสุด) จะต้องยาวเท่ากับเส้นอื่น ๆ ทั้ง $k$ เส้น นั่นคือเราจะได้ว่า

$c(e_{1})=2\cdot c(e_{2})=3\cdot c(e_{3})=\cdots =k\cdot c(e_{k})$

เมื่อ $e_{i}$ คือ edge แรกใน path ที่มีจำนวน edge เท่ากับ $i$ edges (สังเกตว่าทุก ๆ edge ใน path เดี่ยวกัน จะต้องมี congestion เท่ากัน)

สังเกตว่า ผลลัพธ์ที่เราได้ จะต้องเป็น flow ที่มีขนาด k หน่วย จากจุดสมดุลย์ข้างต้น เราส่ง flow ไปแล้วทั้งสิ้นเท่ากับ

$c(e_{1})+c(e_{2})+\cdots +c(e_{k})$ หน่วย ดังนั้นเราจะ scale flow ดังกล่าวลง เพื่อให้ได้ผลรวมเท่ากับ $k$ เราจะต้องหาตัวคูณ $\alpha$ ที่สอดคล้องกับ

$\alpha \cdot (c(e_{1})+c(e_{2})+\cdots +c(e_{k}))=k$ นั่นคือ $\alpha ={\frac {k}{c(e_{1})+c(e_{2})+\cdots +c(e_{k})}}$

จัดนิพจน์ใหม่ ตามสมการด้านบน โดยแทนค่า $c(e_{i})=c(e_{1})/i$ เราจะได้ว่า

$\alpha ={\frac {k}{c(e_{1})+{\frac {c(e_{1})}{2}}+{\frac {c(e_{1})}{3}}+\cdots +{\frac {c(e_{1})}{k}}}}={\frac {k}{c(e_{1})\left(1+{\frac {1}{2}}+{\frac {1}{3}}+\cdots +{\frac {1}{k}}\right)}}$

สังเกตว่าจำนวน flow ทั้งหมดที่ผ่านเส้นเชื่อม $e_{1}$ หลังจากการ scale ด้วย $\alpha$ แล้ว จะมีค่าเท่ากับ

$\alpha \cdot c(e_{1})={\frac {k}{1+{\frac {1}{2}}+{\frac {1}{3}}+\cdots +{\frac {1}{k}}}}\approx k/{\ln k}$

ซึ่งดีกว่าค่า congestion $k$ ในตอนแรก