01204512/weight bipartite matching

เอกสารนี้เป็นส่วนหนึ่งของวิชา 01204512

เราจะพิจารณาปัญหา maximum weighted perfect bipartite matching ให้ bipartite graph $G=(U\cup V,E)$ ที่มีน้ำหนัก $w(u,v)$ บนเส้นเชื่อม $(u,v)\in E$

เราเขียน integer program ของปัญหาดังกล่าวได้ดังนี้ เราจะให้ตัวแปร $x(u,v)$ มีค่าเป็น 1 ถ้าเราเลือกเส้นเชื่อมนั้นใน matching และเป็น 0 ถ้าเราไม่ได้เลือก

• Minimize $\sum _{(u,v)\in E}w(u,v)\cdot x(u,v)$
• Subject to:
  • For all $u\in U$,     $\sum _{(u,v)\in E}x(u,v)=1$
  • For all $v\in V$,     $\sum _{(u,v)\in E}x(u,v)=1$
  • For all $(u,v)\in E$,     $x(u,v)\in \{0,1\}$

เราจะ relax ปัญหาให้เป็น linear program โดยเปลี่ยนเงื่อนไขสุดท้ายเป็น

• • For all $(u,v)\in E$,     $x(u,v)\geq 0$