01204512/congestion1

หน้านี้เป็นเอกสารประกอบวิชา 01204512

ปัญหา 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$