01204512/congestion2

เอกสารนี้สำหรับรายวิชา 01204512 อ้างอิงจาก http://www.cs.berkeley.edu/~satishr/cs270/sp12/ lecture 1

ในเอกสาร 01204512/congestion1 เราวิเคราะห์กรณีกราฟพิเศษ ที่มี paths ความยาว $1,2,\ldots ,k$ เชื่อมระหว่างจุดปลาย

ในส่วนนี้เราจะวิเคราะห์กรณีทั่วไป จะวิเคราะห์ผ่านทางปัญหาทวิภาค (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\}$