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$ ในตอนแรก

การปรับระยะทางเป็นกำลังสอง

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

ในกรณีนี้ เราจะได้ว่า เส้นทางทุกเส้นจะมีความยาวเท่ากันก็ต่อเมื่อ

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

หรือ $c(e_{i})={\sqrt {c(e_{1})^{2}/i}}=c(e_{1})/{\sqrt {i}}$

เราแทนค่านี้ลงไปใหม่ ในการวิเคราะห์เดิมในกรณีที่ปรับค่าความยาวเป็นเชิงเสิ้น เราจะได้ว่า

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

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

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

สังเกตว่า ${\frac {1}{\sqrt {i}}}\geq {\frac {1}{\sqrt {k}}}$ เมื่อ $1\leq i\leq k$ ดังนั้น

${\frac {1}{1}}+{\frac {1}{\sqrt {2}}}+{\frac {1}{\sqrt {3}}}+\cdots +{\frac {1}{\sqrt {k}}}\geq k\cdot {\frac {1}{\sqrt {k}}}={\sqrt {k}}$

ดังนั้น ค่า congestion บน $e_{1}$ หลักการ scale จะมีค่าไม่เกิน $k/{\sqrt {k}}={\sqrt {k}}$

การปรับระยะทางแบบยกกำลัง

ถ้าเราจะปรับความยาวให้มากขึ้น โดยให้ $\ell (e)=2^{c(e)}$ สำหรับทุก ๆ เส้นเชื่อม

ในกรณีนี้ เราจะได้ว่า เส้นทางทุกเส้นจะมีความยาวเท่ากันก็ต่อเมื่อ

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

หรือ $c(e_{i})=\log 2^{c(e_{1})}/i=c(e_{1})-\log i$ เมื่อนำสมการนี้เข้าไปแทนในการวิเคราะห์เราสามารถแสดงได้ไม่ยากว่า congestion ที่มากที่สุด จะมีค่าไม่เกิน $O(\log k)$