ผลต่างระหว่างรุ่นของ "วัฒนา จินดาหลวง"
ไปยังการนำทาง
ไปยังการค้นหา
| แถว 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> | + | ให้กราฟ 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> เอกสารอ้างอิง [ ] |
====Online k-server Problem==== | ====Online k-server Problem==== | ||
รุ่นแก้ไขเมื่อ 15:08, 10 มีนาคม 2552
เนื้อหา
ประวัติ
ชื่อ: วัฒนา จินดาหลวง
ชื่อเล่น: อ๋อย
งานวิจัยที่สนใจ: ด้าน approximation algorithms, graph theory, network design
ปัญหาที่เคยศึกษา
Metric Uncapacitated Facility Location Problem
นิยามของปัญหา: ให้กราฟ G=(V,E) ที่แต่ละ edge e=(i,j) E มีcost dij ที่ satisfy triangle inequality, set ของ cities C V, set ของ facilities F V, แต่ละ facility i F มี cost ในการเปิดเป็น fi, แต่ละ city j C มี cost ในการ connect กับ facility i ใน F เป็น dij ต้องการหา set F' F ที่ต้องเปิดและ assign แต่ละ city ให้กับบาง facility i' F' โดยที่ ผลรวมของ cost ในการเปิดทุก ๆ facility ใน F' และ cost ในการ connect city j' เข้ากับ facility i' F' น้อยที่สุด นั่นคือ minimize เอกสารอ้างอิง [ ]
Online k-server Problem
ปัญหาที่ศึกษาตอนนี้
Movement Problem
Moblile Facility Location Problem
