01204512/weight bipartite matching

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

Primal และ Dual linear programs

เราจะพิจารณาปัญหา 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 ถ้าเราไม่ได้เลือก

• Maximize $\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$

จาก linear program ดังกล่าว เราสามารถหา dual program ได้ โดยสร้างตัวแปร $a(u)$ สำหรับทุก ๆ $u\in U$ (เงื่อนไขแรก) และตัวแปร $b(v)$ สำหรับทุก ๆ $v\in V$ (เงื่อนไขที่สอง) เนื่องจากเงื่อนไขเป็นสมการ (ไม่ใช่ อสมการ) ตัวแปร dual ทั้งสองจะเป็นแบบไม่ระบุขอบเขต

ด้านล่างเป็น dual linear program

• Minimize $\sum _{u\in U}a(u)+\sum _{v\in V}b(v)$
• Subject to:
  • for all $(u,v)\in E$,     $a(u)+b(v)\geq w(u,v)$

Complementary slackness

เงื่อนไข complementary slackness บอกเราว่าที่คู่ของคำตอบที่เป็น optimal solutions ของคู่ primal/dual linear programs, ถ้าตัวแปรใน primal มีค่าไม่เท่ากับศูนย์ เงื่อนไขที่สอดคล้องกับตัวแปรนั้นใน dual จะต้อง tight, นั่นคือเป็นจริงด้วยเครื่องหมายเท่ากับ

ในกรณีนี้ นั่นคือ ใน optimal solution ถ้า $x(u,v)\neq 0$, แล้วเราจะได้ว่า $a(u)+b(v)=w(u,v)$

เราจะพยายามใช้ complementary slackness นำทางเราไปสู่คำตอบ โดยเราจะเลือกเส้นเชื่อมใส่ใน matching ก็ต่อเมื่อตัวแปร dual ของเราบนเส้นเชื่อมนั้นสอดคล้องกับ complementary slackness นั่นคือ เส้นเชื่อมนั้น tight (i.e., $a(u)+b(v)=w(u,v)$)