วัฒนา จินดาหลวง - ประวัติรุ่นแก้ไข

Aoy: /* Metric k-median Problem */

2010-06-30T10:17:59Z

Metric k-median Problem

Aoy: /* Metric Uncapacitated Facility Location Problem (UFL) */

2010-06-30T10:17:49Z

Metric Uncapacitated Facility Location Problem (UFL)

Aoy: /* เอกสารอ้างอิง */

2010-06-30T10:17:31Z

เอกสารอ้างอิง

Aoy: /* Metric Uncapacitated Facility Location Problem (UFL) */

2010-06-30T10:16:17Z

Metric Uncapacitated Facility Location Problem (UFL)

Aoy: /* เอกสารอ้างอิง */

2010-06-30T10:16:03Z

เอกสารอ้างอิง

Aoy: /* Metric Uncapacitated Facility Location Problem (UFL) */

2010-06-30T10:15:18Z

Metric Uncapacitated Facility Location Problem (UFL)

Aoy: /* เอกสารอ้างอิง */

2010-06-30T10:15:02Z

เอกสารอ้างอิง

Aoy: /* เอกสารอ้างอิง */

2010-06-30T10:12:02Z

เอกสารอ้างอิง

Aoy: /* เอกสารอ้างอิง */

2010-06-30T10:11:40Z

เอกสารอ้างอิง

Aoy: /* เอกสารอ้างอิง */

2010-06-30T10:10:14Z

เอกสารอ้างอิง

@@ แถว 33: / แถว 33: @@
+k
-เอกสารอ้างอิง [ ][ ]
+เอกสารอ้างอิง [JV2001]
 === ปัญหาที่ศึกษาตอนนี้ ===

@@ แถว 12: / แถว 12: @@
 นิยามของปัญหา:
-ให้กราฟ G=(V,E) ที่แต่ละ edge e=(i,j) <math>\in</math> E มีcost dij ที่ satisfy triangle inequality, set ของ cities C <math>\subseteq</math> V, set ของ facilities F <math>\subseteq</math> V, แต่ละ facility i <math>\in</math> F มี cost ในการเปิดเป็น fi, แต่ละ city j <math>\in</math> C มี cost ในการ connect กับ facility i ใน F เป็น dij ต้องการหา set F' <math>\subseteq</math> F ที่ต้องเปิดและ assign แต่ละ city ให้กับบาง facility i'<math>\in</math> F' โดยที่ ผลรวมของ cost ในการเปิดทุก ๆ facility ใน  F' และ cost ในการ connect city j' เข้ากับ facility i'<math>\in</math> F' น้อยที่สุด นั่นคือ minimize <math>\sum_{i' \in F'}{fi'}+ \sum_{i' \in F', j' \in C} {di'j'}</math>   เอกสารอ้างอิง[STA1997][C1998]
+ให้กราฟ G=(V,E) ที่แต่ละ edge e=(i,j) <math>\in</math> E มีcost dij ที่ satisfy triangle inequality, set ของ cities C <math>\subseteq</math> V, set ของ facilities F <math>\subseteq</math> V, แต่ละ facility i <math>\in</math> F มี cost ในการเปิดเป็น fi, แต่ละ city j <math>\in</math> C มี cost ในการ connect กับ facility i ใน F เป็น dij ต้องการหา set F' <math>\subseteq</math> F ที่ต้องเปิดและ assign แต่ละ city ให้กับบาง facility i'<math>\in</math> F' โดยที่ ผลรวมของ cost ในการเปิดทุก ๆ facility ใน  F' และ cost ในการ connect city j' เข้ากับ facility i'<math>\in</math> F' น้อยที่สุด นั่นคือ minimize <math>\sum_{i' \in F'}{fi'}+ \sum_{i' \in F', j' \in C} {di'j'}</math>   เอกสารอ้างอิง[STA1997][C1998][JV2001]
 ====Online k-server Problem====

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 10:17, 30 มิถุนายน 2553
แถว 74:		แถว 74:

	[C1998]Chudak, F.A. 1998. Improved approximation algorithms for uncapacitated facility location. IPCO VI. 1442: 180-194.		[C1998]Chudak, F.A. 1998. Improved approximation algorithms for uncapacitated facility location. IPCO VI. 1442: 180-194.
		+
		+	[JV2001]Jain, K. and V.V. Vazirani. 2001. Approximation algorithms for metric facility location and k-median problems using the primal-dual schema and lagrangian relaxation. Journal of the ACM. 48(2): 274-292.

@@ แถว 12: / แถว 12: @@
 นิยามของปัญหา:
-ให้กราฟ G=(V,E) ที่แต่ละ edge e=(i,j) <math>\in</math> E มีcost dij ที่ satisfy triangle inequality, set ของ cities C <math>\subseteq</math> V, set ของ facilities F <math>\subseteq</math> V, แต่ละ facility i <math>\in</math> F มี cost ในการเปิดเป็น fi, แต่ละ city j <math>\in</math> C มี cost ในการ connect กับ facility i ใน F เป็น dij ต้องการหา set F' <math>\subseteq</math> F ที่ต้องเปิดและ assign แต่ละ city ให้กับบาง facility i'<math>\in</math> F' โดยที่ ผลรวมของ cost ในการเปิดทุก ๆ facility ใน  F' และ cost ในการ connect city j' เข้ากับ facility i'<math>\in</math> F' น้อยที่สุด นั่นคือ minimize <math>\sum_{i' \in F'}{fi'}+ \sum_{i' \in F', j' \in C} {di'j'}</math>   เอกสารอ้างอิง[STA1997]
+ให้กราฟ G=(V,E) ที่แต่ละ edge e=(i,j) <math>\in</math> E มีcost dij ที่ satisfy triangle inequality, set ของ cities C <math>\subseteq</math> V, set ของ facilities F <math>\subseteq</math> V, แต่ละ facility i <math>\in</math> F มี cost ในการเปิดเป็น fi, แต่ละ city j <math>\in</math> C มี cost ในการ connect กับ facility i ใน F เป็น dij ต้องการหา set F' <math>\subseteq</math> F ที่ต้องเปิดและ assign แต่ละ city ให้กับบาง facility i'<math>\in</math> F' โดยที่ ผลรวมของ cost ในการเปิดทุก ๆ facility ใน  F' และ cost ในการ connect city j' เข้ากับ facility i'<math>\in</math> F' น้อยที่สุด นั่นคือ minimize <math>\sum_{i' \in F'}{fi'}+ \sum_{i' \in F', j' \in C} {di'j'}</math>   เอกสารอ้างอิง[STA1997][C1998]
 ====Online k-server Problem====

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 10:16, 30 มิถุนายน 2553
แถว 72:		แถว 72:

	[STA1997]Shmoys, D.B., E. Tardos and K. Aardal. 1997. Approximation algorithms for facility location problems. pp. 265-274. In 29th ACM Symposium on Theory of Computing.		[STA1997]Shmoys, D.B., E. Tardos and K. Aardal. 1997. Approximation algorithms for facility location problems. pp. 265-274. In 29th ACM Symposium on Theory of Computing.
		+
		+	[C1998]Chudak, F.A. 1998. Improved approximation algorithms for uncapacitated facility location. IPCO VI. 1442: 180-194.

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 10:15, 30 มิถุนายน 2553
แถว 70:		แถว 70:

	[DHMSOZ07] Demaine, E.D., M. Hajiaghayi, H. Mahini, A. Sayedi-Roshkhar, S. Oveisgharan and M. Zadimoghaddam. 2007. Minimizing Movement. In ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, Louisianna.		[DHMSOZ07] Demaine, E.D., M. Hajiaghayi, H. Mahini, A. Sayedi-Roshkhar, S. Oveisgharan and M. Zadimoghaddam. 2007. Minimizing Movement. In ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, Louisianna.
		+
		+	[STA1997]Shmoys, D.B., E. Tardos and K. Aardal. 1997. Approximation algorithms for facility location problems. pp. 265-274. In 29th ACM Symposium on Theory of Computing.

@@ แถว 68: / แถว 68: @@
 === เอกสารอ้างอิง ===
 [MMS1990] Mark S. Manasse,Lyle A.McGeoch, and Daniel D Slestor;"Competitive Algorithms for Server Problems",1990.
 Demaine, E.D., M. Hajiaghayi, H. Mahini, A. Sayedi-Roshkhar, S. Oveisgharan and M. Zadimoghaddam.  2007.  Minimizing Movement.  In ACM-SIAM Symposium on Discrete Algorithms.  Society for Industrial and Applied Mathematics, Louisianna.

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 10:11, 30 มิถุนายน 2553
แถว 68:		แถว 68:
	=== เอกสารอ้างอิง ===		=== เอกสารอ้างอิง ===
	[MMS1990] Mark S. Manasse,Lyle A.McGeoch, and Daniel D Slestor;"Competitive Algorithms for Server Problems",1990.		[MMS1990] Mark S. Manasse,Lyle A.McGeoch, and Daniel D Slestor;"Competitive Algorithms for Server Problems",1990.
		+	Demaine, E.D., M. Hajiaghayi, H. Mahini, A. Sayedi-Roshkhar, S. Oveisgharan and M. Zadimoghaddam. 2007. Minimizing Movement. In ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, Louisianna.

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 10:10, 30 มิถุนายน 2553
แถว 67:		แถว 67:

	=== เอกสารอ้างอิง ===		=== เอกสารอ้างอิง ===
−	[~~MMS1989~~] Mark S. Manasse,Lyle A.McGeoch, and Daniel D Slestor;"Competitive Algorithms for Server Problems",~~1989~~.	+	[MMS1990] Mark S. Manasse,Lyle A.McGeoch, and Daniel D Slestor;"Competitive Algorithms for Server Problems",1990.