01204512/weight bipartite matching - ประวัติรุ่นแก้ไข

Jittat: /* Complementary slackness */

2012-08-08T04:47:28Z

Complementary slackness

Jittat เมื่อ 04:35, 8 สิงหาคม 2555

2012-08-08T04:35:49Z

Jittat เมื่อ 04:34, 8 สิงหาคม 2555

2012-08-08T04:34:44Z

Jittat เมื่อ 04:29, 8 สิงหาคม 2555

2012-08-08T04:29:37Z

Jittat เมื่อ 04:28, 8 สิงหาคม 2555

2012-08-08T04:28:30Z

Jittat เมื่อ 04:19, 8 สิงหาคม 2555

2012-08-08T04:19:26Z

Jittat: หน้าที่ถูกสร้างด้วย 'เราจะพิจารณาปัญหา maximum weighted perfect bipartite matching ให้ bipartite graph $G = (U...'$

2012-08-08T04:18:58Z

หน้าที่ถูกสร้างด้วย 'เราจะพิจารณาปัญหา maximum weighted perfect bipartite matching ให้ bipartite graph <math>G = (U...'

หน้าใหม่

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

เราเขียน integer program ของปัญหาดังกล่าวได้ดังนี้

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 04:47, 8 สิงหาคม 2555
แถว 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==

@@ แถว 1: / แถว 1: @@
 : ''เอกสารนี้เป็นส่วนหนึ่งของวิชา [[01204512]]''
 เราจะพิจารณาปัญหา maximum weighted perfect bipartite matching  ให้ bipartite graph <math>G = (U\cup V,E)</math> ที่มีน้ำหนัก <math>w(u,v)</math> บนเส้นเชื่อม <math>(u,v)\in E</math>
@@ แถว 23: / แถว 25: @@
 * Subject to:
 ** for all <math>(u,v)\in E</math>, &nbsp;&nbsp;&nbsp; <math>a(u)+b(v)\geq w(u,v)</math>

@@ แถว 5: / แถว 5: @@
 เราเขียน integer program ของปัญหาดังกล่าวได้ดังนี้  เราจะให้ตัวแปร <math>x(u,v)</math> มีค่าเป็น 1 ถ้าเราเลือกเส้นเชื่อมนั้นใน matching และเป็น 0 ถ้าเราไม่ได้เลือก
-* Minimize <math>\sum_{(u,v)\in E} w(u,v)\cdot x(u,v)</math>
+* Maximize <math>\sum_{(u,v)\in E} w(u,v)\cdot x(u,v)</math>
 * Subject to:
-** For all <math>u\in U</math>, &nbsp;&nbsp;&nbsp; <math>\sum_{(u,v)\in E} x(u,v)=1</math>
+** for all <math>u\in U</math>, &nbsp;&nbsp;&nbsp; <math>\sum_{(u,v)\in E} x(u,v)=1</math>
-** For all <math>v\in V</math>, &nbsp;&nbsp;&nbsp; <math>\sum_{(u,v)\in E} x(u,v)=1</math>
+** for all <math>v\in V</math>, &nbsp;&nbsp;&nbsp; <math>\sum_{(u,v)\in E} x(u,v)=1</math>
-** For all <math>(u,v)\in E</math>, &nbsp;&nbsp;&nbsp; <math>x(u,v)\in\{0,1\}</math>
+** for all <math>(u,v)\in E</math>, &nbsp;&nbsp;&nbsp; <math>x(u,v)\in\{0,1\}</math>
 เราจะ relax ปัญหาให้เป็น linear program โดยเปลี่ยนเงื่อนไขสุดท้ายเป็น
 ** For all <math>(u,v)\in E</math>, &nbsp;&nbsp;&nbsp; <math>x(u,v)\geq 0</math>

@@ แถว 7: / แถว 7: @@
 * Minimize <math>\sum_{(u,v)\in E} w(u,v)\cdot x(u,v)</math>
 * Subject to:
-** For all <math>u\in U</math>, <math>\sum_{(u,v)\in E} x(u,v)=1</math>
+** For all <math>u\in U</math>, &nbsp;&nbsp;&nbsp; <math>\sum_{(u,v)\in E} x(u,v)=1</math>
-** For all <math>v\in V</math>, <math>\sum_{(u,v)\in E} x(u,v)=1</math>
+** For all <math>v\in V</math>, &nbsp;&nbsp;&nbsp; <math>\sum_{(u,v)\in E} x(u,v)=1</math>
-** For all <math>(u,v)\in E</math> <math>x(u,v)\in\{0,1\}</math>
+** For all <math>(u,v)\in E</math>, &nbsp;&nbsp;&nbsp; <math>x(u,v)\in\{0,1\}</math>

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 04:28, 8 สิงหาคม 2555
แถว 3:		แถว 3:
	เราจะพิจารณาปัญหา maximum weighted perfect bipartite matching ให้ bipartite graph <math>G = (U\cup V,E)</math> ที่มีน้ำหนัก <math>w(u,v)</math> บนเส้นเชื่อม <math>(u,v)\in E</math>		เราจะพิจารณาปัญหา maximum weighted perfect bipartite matching ให้ bipartite graph <math>G = (U\cup V,E)</math> ที่มีน้ำหนัก <math>w(u,v)</math> บนเส้นเชื่อม <math>(u,v)\in E</math>

−	เราเขียน integer program ของปัญหาดังกล่าวได้ดังนี้	+	เราเขียน integer program ของปัญหาดังกล่าวได้ดังนี้ เราจะให้ตัวแปร <math>x(u,v)</math> มีค่าเป็น 1 ถ้าเราเลือกเส้นเชื่อมนั้นใน matching และเป็น 0 ถ้าเราไม่ได้เลือก
		+
		+	* Minimize <math>\sum_{(u,v)\in E} w(u,v)\cdot x(u,v)</math>
		+	* Subject to:
		+	** For all <math>u\in U</math>, <math>\sum_{(u,v)\in E} x(u,v)=1</math>
		+	** For all <math>v\in V</math>, <math>\sum_{(u,v)\in E} x(u,v)=1</math>
		+	** For all <math>(u,v)\in E</math> <math>x(u,v)\in\{0,1\}</math>

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 04:19, 8 สิงหาคม 2555
แถว 1:		แถว 1:
		+	: ''เอกสารนี้เป็นส่วนหนึ่งของวิชา [[01204512]]''
		+
	เราจะพิจารณาปัญหา maximum weighted perfect bipartite matching ให้ bipartite graph <math>G = (U\cup V,E)</math> ที่มีน้ำหนัก <math>w(u,v)</math> บนเส้นเชื่อม <math>(u,v)\in E</math>		เราจะพิจารณาปัญหา maximum weighted perfect bipartite matching ให้ bipartite graph <math>G = (U\cup V,E)</math> ที่มีน้ำหนัก <math>w(u,v)</math> บนเส้นเชื่อม <math>(u,v)\in E</math>

	เราเขียน integer program ของปัญหาดังกล่าวได้ดังนี้		เราเขียน integer program ของปัญหาดังกล่าวได้ดังนี้