01204512/congestion2

จาก Theory Wiki
ไปยังการนำทาง ไปยังการค้นหา

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

ในส่วนนี้เราจะวิเคราะห์กรณีทั่วไป จะวิเคราะห์ผ่านทางปัญหาทวิภาค (dual problem) สำหรับการหาปัญหาทวิภาคนี้ เราจะพิจารณาละเอียดต่อไป

สำหรับปัญหา congestion minimization ในปัญหาทวิภาคของปัญหาดังกล่าว เราต้องการหาค่า weight ให้กับทุก ๆ edge โดยที่ผลรวมของ weight มีค่าเท่ากับ 1 นอกจากนี้ ให้ เป็น shortest path ระหว่าง และ ภายใต้ weight เป้าหมายของเราคือพยายามจะ maximize ผลรวมของระยะทางสั้นที่สุดของทุก ๆ คู่

ปัญหาดังกล่าวนิยามได้ดังนี้

  • max
  • subject to:

หมายเหตุ เราเขียน แทนเซต