ผลต่างระหว่างรุ่นของ "01204512/weight bipartite matching"

จาก Theory Wiki
ไปยังการนำทาง ไปยังการค้นหา
 
แถว 27: แถว 27:
  
 
==Complementary slackness==
 
==Complementary slackness==
 +
 +
เงื่อนไข complementary slackness บอกเราว่าที่คู่ของคำตอบที่เป็น optimal solutions ของคู่ primal/dual linear programs, ถ้าตัวแปรใน primal มีค่าไม่เท่ากับศูนย์  เงื่อนไขที่สอดคล้องกับตัวแปรนั้นใน dual จะต้อง tight, นั่นคือเป็นจริงด้วยเครื่องหมายเท่ากับ
 +
 +
ในกรณีนี้ นั่นคือ ใน optimal solution ถ้า <math>x(u,v)\neq 0</math>, แล้วเราจะได้ว่า <math>a(u)+b(v)=w(u,v)</math>
 +
 +
เราจะพยายามใช้ complementary slackness นำทางเราไปสู่คำตอบ โดยเราจะเลือกเส้นเชื่อมใส่ใน matching ก็ต่อเมื่อตัวแปร dual ของเราบนเส้นเชื่อมนั้นสอดคล้องกับ complementary slackness นั่นคือ เส้นเชื่อมนั้น tight (i.e., <math>a(u)+b(v)=w(u,v)</math>)
  
 
==Primal-dual algorithms==
 
==Primal-dual algorithms==

รุ่นแก้ไขปัจจุบันเมื่อ 04:47, 8 สิงหาคม 2555

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

Primal และ Dual linear programs

เราจะพิจารณาปัญหา maximum weighted perfect bipartite matching ให้ bipartite graph ที่มีน้ำหนัก บนเส้นเชื่อม

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

  • Maximize
  • Subject to:
    • for all ,    
    • for all ,    
    • for all ,    


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

    • For all ,    

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

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

  • Minimize
  • Subject to:
    • for all ,    

Complementary slackness

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

ในกรณีนี้ นั่นคือ ใน optimal solution ถ้า , แล้วเราจะได้ว่า

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

Primal-dual algorithms